# Homework 15 February, 2022 ## Focus on previous days' unsolved problems first. 1. **Minimum Passes of Matrix:** You are given an 2D array(matrix) of integers of potentially unequal height and width. Write a program that calculates minimum number of passes required to convert all negative integers in the matrix to positive integers. Note: We don't consider `0` either positive or negative. **Rule:** A negative integer can only be converted to positive if it's adjacent(left,right,top,bottom, BUT NOT diagonal) to a positive element. Regardless of how many passes are run, if there is any negative integer that can't be converted to positive, program should output `-1`. **Input and Output:** 1. ```php [ [0, -1, -3, 2, 0], [1, -2, -5, -1, -3], [3, 0, 0, -4, -1] ] ``` ``` 3 ``` 2. ```php [ [1, 0, 0, -2, -3], [-4, -5, -6, -2, -1], [0, 0, 0, 0, -1], [-1, 0, 3, 0, 3] ] ``` ``` -1 ``` 3. ```php [ [-2, -3, -4, -1, -9], [-4, -3, -4, -1, -2], [-6, -7, -2, -1, -1], [0, 0, 0, 0, -3], [1, -2, -3, -6, -1] ] ``` ``` 12 ``` 2. **Cycle In Graph:** You are given an Adjacency List of a **unweighted** and **directed** graph. In the given list, each index `i` in the list contains vertex(node) `i`'s ***outbound*** edges. Each edge is represented by a integer that signifies an index (a destination vertex) in the list that this vertex is connected to. Write a program to output a boolean showing if the graph contains a cycle. (There can be self cycle). Hint: Start a DFS tree, if you encounter a edge going to an Ancestor Node, then cycle is detected and program completes. **Input and Output:** 1. ```php [ [1, 3], [2, 3, 4], [0], [], [2, 5], [] ] ``` ``` true ``` 2. ```php [ [1], [2, 3, 4, 5, 6, 7], [], [2, 7], [5], [], [4], [] ] ``` ``` false ``` 3. ```php [ [0] ] ``` ``` true ``` 3. **Levenshtein Distance:** Definition: the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion or substitution) required to change one word into the other. **Input (string one, string two) and Output:** - `abc` `yabd` `2` - `abc` `abc` `0` - `biting` `mitten` `4`