# 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
```
Sign in with Wallet
Connect another wallet