# CSPT25 Lecture 14
## [All Paths]

from collections import deque, defaultdict
class Solution:
    """
    Understand
    Plan
    Translate the problem in to graph terminology
    vertices - each index is a vertex
    edges - the value at that index are its neighbors
    weights - n/a
    
    Build your graph
    Easily make an adj list from the input that we are given
    
    Traverse the graph
    DFS/BFS doesn't matter
    just keep track of the path that you're on
    once you find destination node, append the path you took to that node
    in a result list
    """
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        self.allPathsSourceTargetHelper(graph, 0, [0], res)
        return res
        
    def allPathsSourceTargetHelper(self, graph, currNode, currPath, res):
        if currNode == len(graph) - 1:
            res.append(currPath)
        else:
            for neighbor in graph[currNode]:
                newPath = currPath.copy()
                newPath.append(neighbor)
                self.allPathsSourceTargetHelper(graph, neighbor, newPath, res)
    
    def allPathsSourceTargetIterative(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        adjList = self.buildGraph(graph)
        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
        
    def buildGraph(self, inputGraph):
        graph = defaultdict(set)
        for node, neighbors in enumerate(inputGraph):
            for neighbor in neighbors:
                graph[node].add(neighbor)
        return graph

## [Flood Fill]

from collections import deque
class Solution:
    """
    image = [[1,1,1]
             [1,1,0]
             [1,0,1]]
    sr = 1, sc = 1
    newColor = 2
    [[2,2,2]
     [2,2,0]
     [2,0,1]]
---------------------------
     image = [[1,1,1]
              [1,1,1]
              [1,1,1]]
    sr = 1, sc = 1
    newColor = 2
    [[2,2,2]
     [2,2,2]
     [2,2,2]]
-----------------------------
[[1,0,1]
 [0,1,0]
 [1,0,1]]
 sr = 1, sc = 1
newColor = 2
 [[1,0,1]
  [0,2,0]
  [1,0,1]]

Plan
1. Translate the problem into graph terminology
not exactly a graph, but we can treat the matrix similar to a graph
where a node will be an element in the matrix, its neighbors will be its neighboring nodes

2. Build your graph
no need to build our own graph, just use the matrix

3. Traverse your graph
BFT/DFT doesn't matter
start at the given node and change that node's value to the newcolor
also push its neighbors onto the stack if it has the original color of the starting node
keep doing it to all the node's neighbors
    """
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        visited = set()
        colorToChange = image[sr][sc]
        self.floodFillHelper(image, sr, sc, newColor, visited, colorToChange)
        return image
        
    def floodFillHelper(self, image, currRow, currCol, newColor, visited, colorToChange):
        numRows, numCols = len(image), len(image[0])
        if currRow < 0 or currCol < 0 or currRow >= numRows or currCol >= numCols:
            return
        if image[currRow][currCol] != colorToChange:
            return
        if (currRow, currCol) in visited:
            return
        image[currRow][currCol] = newColor
        visited.add((currRow, currCol))
        self.floodFillHelper(image, currRow, currCol + 1, newColor, visited, colorToChange)
        self.floodFillHelper(image, currRow, currCol - 1, newColor, visited, colorToChange)
        self.floodFillHelper(image, currRow + 1, currCol, newColor, visited, colorToChange)
        self.floodFillHelper(image, currRow - 1, currCol, newColor, visited, colorToChange)
    
    def floodFillIterative(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        colorToChange = image[sr][sc]
        queue = deque()
        queue.append((sr, sc))
        numRows, numCols = len(image), len(image[0])
        visited = set()
        while len(queue) > 0:
            curr = queue.popleft()
            currRow, currCol = curr[0], curr[1]
            if curr in visited:
                continue
            if currRow < 0 or currCol < 0 or currRow >= numRows or currCol >= numCols:
                continue
            if image[currRow][currCol] != colorToChange:
                continue
            visited.add(curr)
            image[currRow][currCol] = newColor
            queue.append((currRow + 1, currCol))
            queue.append((currRow, currCol + 1))
            queue.append((currRow - 1, currCol))
            queue.append((currRow, currCol - 1))
        return image