## Path Finding problems using Depth-First-Search DFS

Pathfinding problems have many applications, from computer games, network routing to AI robots. If we want to explore unknown graphs and want to gather more information, DFS is a good choice. DFS is the most simple path exploration of all algorithms. It is appropriate to use during space restriction in complex state representation and acyclic graphs.

## All Paths From Source to Target | 0 | heading |

797. All Paths From Source to Target | 1 | link |

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]). | 2 | paragraph |

3 | image | |

## Intuition | 4 | subheading |

- In the above example, we need to find all paths from 0 node to n-1 node.
- We will use recursive DFS.
- Initialize the visited list to store visited nodes so we don't visit the same node twice.
- Initialize the result list to store paths.
- We follow 3 steps: mark node visited, check if the node is the destination, and explore its unvisited neighbors.
- Our DFS algorithm will first start at node 0 and the destination is 3.
- Below is the python code
| 5 | list |

```
def allPathsSourceTarget(graph):
def dfs(visited, vertex, destination):
visited.append(vertex) #Mark node visted
if destination == vertex: #check if we reached destination
res.append(visited[:]) #copy nodes from visited to result
for u in graph[vertex]:
if u not in visited: #explore its unvisited neighbours
dfs(visited, u, destination)
visited.remove(vertex)
visited = [] # to store visited node
res = [] # to store the result
dfs(visited, 0, len(graph)-1)
return res #res = [[0,1,3],[0,2,3]]
``` | 6 | code |

## Path with Maximum Gold | 7 | heading |

1219. Path with Maximum Gold | 8 | link |

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.Return the maximum amount of gold you can collect under the conditions: | 9 | paragraph |

```
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
``` | 10 | code |

11 | image | |

## Intuition | 12 | subheading |

- Here each node is connected to itself and other nodes. We can visualize the grid in the form of a graph as shown in the above figure.
- This problem can be solved in similar 3 steps as the above problem with little modifications.
- We not only check visited nodes. But we also need to check we stay in the grid.
- Since we have asked for maximum gold we will start the path with sum 0 and keep adding new path node values to the sum.
- Every time we move top, left, right, the bottom cell we check if the node is unvisited and call DFS.
- We want to choose only nodes in the path which give us the maximum sum. So we take a maximum of neighbors and return that value.
| 13 | list |

```
def getMaximumGold(grid):
def dfs(i, j, sum, visited):
#return if check i and j are underflow or overflow or (i,j) already visited
if i < 0 or i >= m or j < 0 or j >= n or not grid[i][j] or (i, j) in visited:
return sum
visited.add((i, j))
sum += grid[i][j] #add to current sum
mx = 0
for x, y in ((i, j + 1), (i , j - 1), (i + 1, j), (i - 1, j)): #check top, left, right, bottom neighbours
mx = max(dfs(x, y, sum, visited), mx) #only choose maximum value
visited.discard((i, j)) #remove from visited
return mx #return total path value
m, n = len(grid), len(grid[0])
maximum_gold = float('-inf')
for i in range(m):
for j in range(n):
#check with every (i,j) node as start node
maximum_gold = max(maximum_gold, dfs(i, j, 0, set()))
return maximum_gold
``` | 14 | code |

## Flood Fill | 7 | heading |

733. Flood Fill | 8 | link |

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor. Return the modified image after performing the flood fill. | 9 | paragraph |

```
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.
``` | 10 | code |

11 | image | |

## Intuition | 12 | subheading |

- Even this problem is similar to the above problems.
- Here we don't require a visited list as we check that value of the cell.
- If the value of the cell is already a new color that means we already visited, we return.
| 13 | list |

```
def floodFill(image, sr, sc, newColor):
def dfs(i,j):
#if going out grid return
if i < 0 or i >= row or j < 0 or j >= col:
return
#color is not same as orginal color or already colored with new color
if image[i][j] != color or image[i][j] == newColor:
return
image[i][j] = newColor
for x,y in ((i, j + 1), (i , j - 1), (i + 1, j), (i - 1, j)):
dfs(x,y)
row = len(image)
col = len(image[0])
color = image[sr][sc]
dfs(sr,sc)
return image
``` | 14 | code |