# CSPT19 Lecture 12
## [All Paths from Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/)

from collections import deque, defaultdict

class Solution:
    """
    Plan
    1. Translate the problem into graph terminology
    vertex - each index in the list given is a node
    edge - each subarray is the node's outgoing edges to its neighbors
    2. Build Your Graph
    Build an adjacency list with the list given
    3. Traverse the Graph
    Type of traversal doesn't matter
    We need to keep track of the path that we're currently on
    Once we encounter the last node, just return the path we took
    to get to the last node
    """
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        self.allPathsSourceTargetHelper(graph, 0, len(graph) - 1, [0], res)
        return res
        
    def allPathsSourceTargetHelper(self, graph, currNode, destinationNode, currPath, res):
        if currNode == destinationNode:
            res.append(currPath)
        else:
            for neighbor in graph[currNode]:
                newPath = currPath.copy()
                newPath.append(neighbor)
                self.allPathsSourceTargetHelper(graph, neighbor, destinationNode, newPath, res)
    
    def iterativeAllPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        queue = deque()
        queue.append((0, [0]))
        res = []
        while len(queue) > 0:
            curr = queue.popleft()
            currNode, currPath = curr[0], curr[1]
            if currNode == destinationNode:
                res.append(currPath)
            else:
                for neighbor in graph[currNode]:
                    newPath = currPath.copy()
                    newPath.append(neighbor)
                    queue.append((neighbor, newPath))
        return res
    
    # returns an adjacency list
    def buildGraph(self, edges):
        graph = defaultdict(set)
        for (node, neighbors) in enumerate(edges):
            for neighbor in neighbors:
                graph[node].add(neighbor)
        return graph

## [Flood Fill](https://leetcode.com/problems/flood-fill/)

from collections import deque
class Solution:
    """
    [[1,1,1],
     [1,1,0],
     [1,0,1]]
    sr = 1, sc = 1, newColor = 2
    output:
    [[2,2,2],
     [2,2,0],
     [2,0,1]]
     
     Plan
     1. Translate the problem into graph terminology
     Not exactly like a graph, but a matrix is very similar to it
     vertex = an element in the matrix
     edges = elements that are right next to it
     2. Build your graph
     No need to build a graph, we can just traverse the actual matrix
     3. Traverse the graph/matrix
     Traversal doesn't matter. All we need to do is traverse from the
     origin point and change the other node's colors if needed
     
     [[1,1,1],
      [1,1,1],
      [1,1,1]]
      
     Runtime: O(m * n)
     Space: O(m * n)
    """
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        colorToChange = image[sr][sc]
        stack = deque()
        stack.append((sr, sc))
        numRows, numCols = len(image), len(image[0])
        visited = set()
        while len(stack) > 0:
            currPoint = stack.pop()
            currRow, currCol = currPoint[0], currPoint[1]
            if currPoint in visited:
                continue
            if currRow < 0 or currRow >= numRows or currCol < 0 or currCol >= numCols:
                continue
            if image[currRow][currCol] != colorToChange:
                continue
            visited.add(currPoint)
            image[currRow][currCol] = newColor
            stack.append((currRow - 1, currCol))
            stack.append((currRow + 1, currCol))
            stack.append((currRow, currCol - 1))
            stack.append((currRow, currCol + 1))
        return image