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

from collections import deque

class Solution:
    """
    Understand
    
    Plan
    1. Translate the problem into graph terminology
    vertex - each index in the list
    edges - the list of values in a specified index

    2. Build your graph
    No need to build explicit graph, just index properly into the 
    input array to get the neighbors of the current node
    
    3. Traverse the graph
    We need to do a traversal
    It doesn't matter what type of traversal
    Use a stack to do a DFT on the graph
    Keep track of the current path that we've taken
    
    If we find the destination node, append the path we took to the resulting
    array
    
    Return the resulting array at the end
    """
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        self.allPathsSourceTargetHelper(graph, len(graph) - 1, 0, [0], res)
        return res
    
    def allPathsSourceTargetHelper(self, graph, destinationNode, currNode, currPath, res):
        # base-case: reached destination node
        if currNode == destinationNode:
            res.append(currPath)
        else:
            for neighbor in graph[currNode]:
                newPath = currPath.copy()
                newPath.append(neighbor)
                self.allPathsSourceTargetHelper(graph, destinationNode, neighbor, newPath, res)
    
    # [[1,2],[3],[3],[]]
#     def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
#         stack = deque()
#         stack.append((0, [0]))
#         res = []
#         destinationNode = len(graph) - 1
        
#         while len(stack) > 0:
#             curr = stack.pop()
#             currNode, currPath = curr[0], curr[1]
#             if currNode == destinationNode:
#                 res.append(currPath)
#             else:
#                 for neighbor in graph[currNode]:
#                     newPath = currPath.copy()
#                     newPath.append(neighbor)
#                     stack.append((neighbor, newPath))
#         return res

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

from collections import deque

class Solution:
    """
    Understand
    [[1,1,1],
     [2,2,0], valueToChange = 1, newColor = 2
     [1,0,1]]

    Plan
    1. Translate this into graph terminology
    totally possible to convert into a graph
    node = a pixel
    edges = neighboring pixels (up, down, left, right)
    
    2. Build your graph
    no need to build a graph, just use the matrix to traverse
    
    3. Traverse 
    Start traversing at the starting point, change the color of that starting point
    Traverse the neighbors of that starting point (up, down, left, right)
    If the neighbor has the same original color as the starting point, then change that 
    neighbors color as well
        Repeat until all valid neighbors are flood-filled
        
        
    [[1,1,1],
     [1,1,0], valueToChange = 1, newColor = 2, sr = 1, sc = 1
     [1,0,1]]
    """
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        colorToChange = image[sr][sc]
        queue = deque()
        queue.append((sr, sc))
        visited = set()
        numRows, numColumns = len(image), len(image[0])
        
        while len(queue) > 0:
            currPoint = queue.popleft()
            currRow, currColumn = currPoint[0], currPoint[1]
            if currRow < 0 or currRow >= numRows or currColumn < 0 or currColumn >= numColumns:
                continue
            if image[currRow][currColumn] != colorToChange:
                continue
            if currPoint in visited:
                continue
            visited.add(currPoint)
            image[currRow][currColumn] = newColor
            queue.append((currRow + 1, currColumn))
            queue.append((currRow - 1, currColumn))
            queue.append((currRow, currColumn + 1))
            queue.append((currRow, currColumn - 1))
        return image