# CSPT23 Lecture 14
## [All Paths](https://leetcode.com/problems/all-paths-from-source-to-target/)

from collections import deque, defaultdict
class Solution:
    """
    graph = [[1,2],[3],[3],[]]
    output = [[0,1,3],[0,2,3]]
    
    graph = [[]]
    output = [[0]]
    
    graph = [[1], [2], []]
    output = [[0,1,2]]
    
    graph = [[1], [], []]
    output = []
    
    Plan
    1. Translate the problem into graph terminology
    graph = [[1,2],[3],[3],[]]
    vertices - each index in the outer list
    edges - the values inside the inner list
    2. Build Your Graph
    Not needed to build our own graph
    3. Traverse the Graph
    Do a search for the last node
    Type of search doesn't matter
    
    Runtime: O(n)
    Space:
    """
    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 allPathsSourceTargetIterative(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        # adjacencyList = 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, graph):
        adjacencyList = defaultdict(set)
        for (node, neighbors) in enumerate(graph):
            for neighbor in neighbors:
                adjacencyList[node].add(neighbor)
        return adjacencyList

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

from collections import deque
class Solution:
    """
    Understand
    [[1,1,1],
     [1,1,0],
     [1,0,1]] 
     sr = 1, sc = 1, newColor = 2
    [[2,2,2],
     [2,2,0],
     [2,0,1]]
     Plan
     Use a stack to keep flood-filling from the starting coordinate.
     Use a visited set, to avoid processing the same coordinates
    """
    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, numCols = len(image), len(image[0])
        while len(queue) > 0:
            currPoint = queue.popleft()
            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
            image[currRow][currCol] = newColor
            visited.add(currPoint)
            queue.append((currRow + 1, currCol))
            queue.append((currRow - 1, currCol))
            queue.append((currRow, currCol + 1))
            queue.append((currRow, currCol - 1))
        return image