---
# System prepended metadata

title: CSPT21 Lecture 14

---

# CSPT21 Lecture 14
## [All Paths From Source to Target](https://leetcode.com/problems/all-paths-from-source-to-target/)
```
from collections import deque

class Solution:
    """
    Plan
    1. Translate the problem into graph terminology
    vertices - each index in the list
    edges - each element in the sublist is an outgoing edge of that node at index i
    weight - n/a
    
    2. Build your graph
    - You can build your own graph using an adjacency list
    - OR you can just traverse the nested list
    
    3. Traverse the graph
    traversal doesn't matter since we're looking for all possible paths
    use a DFS
    use an auxilliary array and also put it in the stack to keep track of the path
    to get to the current node
    
    [[1,2],
     [3],
     [3],
     []]
    """
    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 bfsAllPathsSourceTarget(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
    
    def implicitAllPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        stack = deque()
        stack.append((0, [0]))
        res = []
        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
    
    def explicitAllPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        destinationNode = len(graph) - 1
        graph = self.buildGraph(graph)
        stack = deque()
        stack.append((0, [0]))
        res = []
        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
        
    def buildGraph(self, edges):
        graph = {}
        for (node, neighbors) in enumerate(edges):
            graph[node] = set()
            for neighbor in neighbors:
                graph[node].add(neighbor)
        return graph
```


## [Flood Fill](https://leetcode.com/problems/flood-fill/)
```
from collections import deque

class Solution:
    """
    [[2,2,2],
     [2,2,0],
     [2,0,1]]
     
    Plan
    1. Translate the problem into graph terminology
    vertices - pixel
    edges - neighboring pixels
    weight - n/a
    
    2. Build your graph
    No need to build a graph, just traverse the image given
    
    3. Traverse the graph
    It doesn't matter, as long as you traverse all the neighboring pixels that have the same value as the starting pixel
    
    [[0,0,0],
     [0,1*,1]]
1
1
1
    """
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        visited = set()
        self.floodFillHelper(image, sr, sc, image[sr][sc], newColor, visited)
        return image
    
    def floodFillHelper(self, image, currRow, currCol, colorToChange, newColor, visited):
        numRows, numCols = len(image), len(image[0])
        if currRow < 0 or currRow >= numRows or currCol < 0 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 - 1, currCol, colorToChange, newColor, visited)
        self.floodFillHelper(image, currRow + 1, currCol, colorToChange, newColor, visited)
        self.floodFillHelper(image, currRow, currCol - 1, colorToChange, newColor, visited)
        self.floodFillHelper(image, currRow, currCol + 1, colorToChange, newColor, visited)
    
    
    def bftFloodFill(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:
            currPixel = queue.popleft()
            if currPixel in visited:
                continue
            currRow, currCol = currPixel[0], currPixel[1]
            image[currRow][currCol] = newColor
            visited.add(currPixel)
            
            topRow = currRow - 1
            if topRow >= 0 and image[topRow][currCol] == colorToChange:
                queue.append((topRow, currCol))
            
            bottomRow = currRow + 1
            if bottomRow < numRows and image[bottomRow][currCol] == colorToChange:
                queue.append((bottomRow, currCol))
            
            leftCol = currCol - 1
            if leftCol >= 0 and image[currRow][leftCol] == colorToChange:
                queue.append((currRow, leftCol))
            
            rightCol = currCol + 1
            if rightCol < numCols and image[currRow][rightCol] == colorToChange:
                queue.append((currRow, rightCol))
        return image

    def dftFloodFill(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:
            currPixel = stack.pop()
            if currPixel in visited:
                continue
            currRow, currCol = currPixel[0], currPixel[1]
            image[currRow][currCol] = newColor
            visited.add(currPixel)
            
            topRow = currRow - 1
            if topRow >= 0 and image[topRow][currCol] == colorToChange:
                stack.append((topRow, currCol))
            
            bottomRow = currRow + 1
            if bottomRow < numRows and image[bottomRow][currCol] == colorToChange:
                stack.append((bottomRow, currCol))
            
            leftCol = currCol - 1
            if leftCol >= 0 and image[currRow][leftCol] == colorToChange:
                stack.append((currRow, leftCol))
            
            rightCol = currCol + 1
            if rightCol < numCols and image[currRow][rightCol] == colorToChange:
                stack.append((currRow, rightCol))
        return image
```