# Deep search

Deep search DFS. When a new node is found, it will immediately traverse the new node. It needs to use stack implementation or recursive implementation equivalent to stack.
If the parent node of the traversal loop has a different record, it can also be used to detect each parent node.
Sometimes we may need to mark the nodes that have been searched to prevent repeated search of a node during traversal. This practice is called state recording or memorization.

## 200. Number of islands

```class Solution {
public:
void dfs(vector<vector<char>>& grid,int m,int n,int i,int j)
{
//If it crosses the border or is a sea area, exit
if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
//Mark as sea area
grid[i][j] = '0';
dfs(grid,m,n,i-1,j);
dfs(grid,m,n,i+1,j);
dfs(grid,m,n,i,j-1);
dfs(grid,m,n,i,j+1);
return ;
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int time = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(grid[i][j] == '1')
{
dfs(grid,m,n,i,j);
time++;
}
}
}
return time;
}
};
```

## 695. Maximum area of the island

Generally speaking, deep search can be divided into main function and auxiliary function.
The main function is used to traverse all search positions to determine whether the search can be started. If so, use the auxiliary function to search.
The auxiliary function is responsible for the recursive call or (stack) implementation of deep search.

```class Solution {
public:
vector<int> direction {-1,0,1,0,-1};
//auxiliary function
int dfs(vector<vector<int>>& grid, int r, int c)
{
if(grid[r][c] == 0) return 0;
//Otherwise, clear the flag
grid[r][c] = 0;
//At this time, the island has an area of 1. Next, conduct a deep search in four directions
int x,y,area = 1;
for(int i = 0; i < 4; i++)
{
//New starting point
x = r + direction[i];
y = c + direction[i+1];
//If you don't cross the border, continue to search deeply
if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size())
area += dfs(grid,x,y);
}
//Finally, return the island area starting from r and c, and clear the island on the map to prevent multiple searches.
return area;
}
//Main function
int maxAreaOfIsland(vector<vector<int>>& grid)
{
if(grid.empty() || grid[0].empty()) return 0;
int max_area = 0;
for(int i = 0; i < grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 1)
{
max_area = max(max_area,dfs(grid,i,j));
}
}
}
return max_area;
}
};
```

Auxiliary functions can also be written in this way. I prefer this way:

```//auxiliary function
int dfs(vector<vector<int>>& grid, int r, int c)
{
//If the point is out of bounds or is a sea area, exit recursion
if(r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0) return 0;
//Otherwise, it means that the point is an island with an area of + 1, and the record is cleared at the same time
grid[r][c] = 0;
//Returns the area result of the starting point of the search at this point
return 1 + dfs(grid,r-1,c) + dfs(grid,r,c+1) + dfs(grid,r+1,c) + dfs(grid,r,c-1);
}
```

## 130. Surrounding areas

```class Solution {
public:
void dfs(vector<vector<char>>& board,int m,int n,int i,int j)
{
//Recursive exit condition
if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X' || board[i][j] == 'A') return;
//Otherwise, mark it and continue the deep search
board[i][j] = 'A';
dfs(board,m,n,i-1,j);
dfs(board,m,n,i+1,j);
dfs(board,m,n,i,j-1);
dfs(board,m,n,i,j+1);
return;
}
void solve(vector<vector<char>>& board) {
int m = board.size();
int n = board[0].size();
//Set all connected 0 parts of the boundary to A with dfs
for(int i = 0; i < m ; i++)
{
dfs(board,m,n,i,0);
dfs(board,m,n,i,n-1);
}
for(int j = 0; j < n ; j++)
{
dfs(board,m,n,0,j);
dfs(board,m,n,m-1,j);
}
//Overwrite operation is performed. Only those with A will not be overwritten
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(board[i][j] == 'A') board[i][j] = 'O';
else board[i][j] = 'X';
}
}
return;
}
};
```

## 547. Number of provinces

Analysis: find the number of connected domains in the undirected graph, and the input matrix is the adjacency matrix of the undirected graph

Deep search idea: traverse all cities. For each city, if the city has not been visited, start the deep first search from the city, and get the cities directly connected to the city through the matrix. These cities belong to the same connected component as the city. Then continue the deep search for these cities until all cities of the same connected component are visited, You can get a province.

```class Solution {
public:
void dfs(vector<vector<int>>& isConnected,int i,vector<bool>& visited) {
for(int j = 0; j < isConnected.size(); j++)
{
//Continue to traverse the vertices adjacent to the vertices, and use the visited array to prevent repeated access
if(isConnected[i][j] == 1 && visited[j] == false)
{
//Mark currently accessed vertices
visited[j] = true;
dfs(isConnected,j,visited);
}
}
return;
}

int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int count = 0;
//Identifies whether vertices are accessed
vector<bool> visited(n,false);
for(int i = 0; i < n; i++)
{
//If the current vertex is not accessed, it indicates a new connected domain. Traverse the connected domain and count + 1
if(!visited[i])
{
dfs(isConnected,i,visited);
count++;
}
}
return count;
}
};
```

## 417. Pacific Atlantic currents

1. The boundary can go to an ocean next to it
In other words, the boundary is connected with the ocean, so it needs to spread from outside to inside to obtain the area connected with the boundary (that is, the position with the same height or higher than the current area)
2. To prevent repeated traversal, add the visited array
3. Put the connected parts into two subsets, one is the area connected with the Pacific Ocean and the other is the area connected with the Atlantic Ocean. Then find the intersection of the two.

```class Solution {
public:
vector<int> direction{-1,0,1,0,-1};
bool Isvaild(int x,int y,vector<vector<int>>& matrix)
{
if(x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()) return true;
else return false;
}
//Auxiliary function
void dfs(vector<vector<int>>& matrix,vector<vector<bool>>& can_reach,int r,int c)
{
//If this point has been traversed, exit
if(can_reach[r][c]) return;
can_reach[r][c] = true;
int x,y;
for(int i = 0; i < 4; i++)
{
x = r + direction[i];
y = c + direction[i+1];
if(Isvaild(x,y,matrix) && matrix[r][c] <= matrix[x][y])
dfs(matrix,can_reach,x,y);
}
}
//Main function
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix)
{
if(matrix.empty() || matrix[0].empty())
return {};
vector<vector<int>> ans;
int m = matrix.size();
int n = matrix[0].size();
//Record the area that can be connected with the p ocean
vector<vector<bool>> can_reach_p(m,vector<bool>(n,false));
//Record the area that can be connected with ocean a
vector<vector<bool>> can_reach_a(m,vector<bool>(n,false));

//Traverse the upper and lower boundaries
for(int i = 0; i < m; i++)
{
//Diffusion deep search
dfs(matrix,can_reach_p,i,0);
dfs(matrix,can_reach_a,i,n-1);
}
//Traverse left and right boundaries
for(int j = 0; j < n; j++)
{
//Diffusion deep search
dfs(matrix,can_reach_p,0,j);
dfs(matrix,can_reach_a,m-1,j);
}
//All results will be traversed and intersected
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(can_reach_p[i][j] && can_reach_a[i][j])
ans.push_back(vector<int>{i,j});
}
}
return ans;
}
};
```

# to flash back

Before going back, I have done some topics, all of which are classic topics. I put them directly here.
Algorithm review (backtracking)

# Wide search

The template is as follows:

```//Calculate the shortest distance from start to target
int BFS(Node start,Node target)
{
queue<Node> q;	//Core data structure
Set<Node> visited; //Avoid going backwards

q.push(start);		//Add starting point to queue
visited.insert(start);
int steps = 0;	//Record diffusion steps
while(!q.empty())
{
//Update steps
step++;
int sz = q.size();
//Spread all nodes in the current queue around
for(int i = 0; i < sz; i++)
{
Node cur = q.front();
q.pop();
//Judge whether to reach the end point
if(cur == target) return step;
{
//If not traversed
if(visited.find(x) != visited.end())
{
q.push(x);
visited.insert(x);
}
}
}
}
}
```

cur.adj represents the node adjacent to cur. Visited is mainly used to prevent going back. The binary tree structure has no pointer from the child node to the parent node, so it will not go back and does not need to be visited.
Unlike depth first search, wide search is traversed layer by layer, so first in first out queues are needed, which are often used to deal with the shortest path problem.

Both deep search and wide search can deal with the problem of accessibility, that is, whether it can reach another node from one node. Because deep search can be implemented quickly by recursion, many people are used to using deep search. However, in practical engineering, recursion is rarely used, which is easy to produce stack overflow.

## 111. Minimum depth of binary tree

start: root node
target: the leaf node closest to the root node

```if(cur.left == nullptr && cur.right == nullptr) //Reached leaf node
```
```class Solution {
public:
int minDepth(TreeNode* root) {
int result = 0;
queue<TreeNode*> que;
if(root == nullptr) return 0;
que.push(root);
while(!que.empty())
{
result++;
int sz = que.size();
for(int i = 0; i < sz; i++)
{
TreeNode* cur = que.front();
que.pop();
//If you reach the end, return the result
if(cur->left == nullptr && cur->right == nullptr) return result;
//Otherwise continue
if(cur->left != nullptr) que.push(cur->left);
if(cur->right != nullptr) que.push(cur->right);
}
}
return result;
}
};
```

## 752. Open the turntable lock

Calculate the minimum number of times to dial out the target state from the initial state "0000". If you can never dial out, return - 1
The list deands contains a set of death numbers. Once the number of the dial wheel is the same as any element in the list, the lock will be permanently locked and can no longer be rotated.
Starting from 0000, according to the idea of breadth, there are eight possibilities to turn once:
1000,9000,0100,0900,...
It can be abstracted into a graph. Each node has 8 adjacent nodes. Find the shortest distance. At this time, BFS can be used.
The following preliminary code is used to find the minimum password combination according to BFS, but it is obviously problematic.

```class Solution {
public:
string plusOne(string s,int j)
{
string result = s;
if(result[j] == '9') result[j] = '0';
else result[j] = result[j] + 1;
return result;
}
string minusOne(string& s,int j)
{
string result = s;
if(result[j] == '0') result[j] = '9';
else result[j] = result[j] - 1;
return result;
}
int openLock(vector<string>& deadends, string target) {
queue<string> q;
string start = "0000";
q.push(start);
int time = 0;
while(!q.empty())
{
time++;
int sz = q.size();
for(int i = 0; i < sz; i++)
{
string cur = q.front();
q.pop();
//Judge whether to reach the end point
if(cur == target) return time;
//Queue the nodes adjacent to a node
for(int j = 0; j < 4; j++)
{
string up = plusOne(cur,j);
q.push(up);
string down = minusOne(cur,j);
q.push(down);
}
}
}
return time;
}
};
```

The existing problems are as follows:
1. You will go back, for example, dial "0000" to "1000", but when you take "1000" out of the queue, you will also dial "0000"
2. Deands are not processed. In principle, these death passwords cannot appear. When encountering these passwords, you need to skip them.
The modified code is as follows:

```class Solution {
public:
string plusOne(string s,int j)
{
string result = s;
if(result[j] == '9') result[j] = '0';
else result[j] = result[j] + 1;
return result;
}
string minusOne(string& s,int j)
{
string result = s;
if(result[j] == '0') result[j] = '9';
else result[j] = result[j] - 1;
return result;
}
int openLock(vector<string>& deadends, string target) {
//Record the death password that needs to be skipped
//Record the passwords that have been exhausted to prevent turning back
set<string> visited;
queue<string> q;
string start = "0000";
q.push(start);
visited.insert(start);
int time = 0;
while(!q.empty())
{
int sz = q.size();
for(int i = 0; i < sz; i++)
{
string cur = q.front();
q.pop();
//Judge whether it is legal
//Judge whether to reach the end point
if(cur == target) return time;
//Add the adjacent nodes of a node to the queue. If they exist, they do not need to be added to the queue
for(int j = 0; j < 4; j++)
{
string up = plusOne(cur,j);
if(visited.find(up) == visited.end())
{
q.push(up);
visited.insert(up);
}
string down = minusOne(cur,j);
if(visited.find(down) == visited.end())
{
q.push(down);
visited.insert(down);
}
}
}
time++;
}
return -1;
}
};
```

# Combination of deep search and wide search

## 934. Shortest Bridge

```class Solution {
public:
vector<int> direction{-1,0,1,0,-1};
void dfs(vector<vector<int>>& A,queue<pair<int,int>>& points,int m,int n,int i,int j)
{
//If the boundary is crossed or traversed, do not continue to traverse to the depth
if(i < 0 || j < 0 || i >= m || j >= n || A[i][j] == 2) return;
//If it is a sea area, insert it into the queue
if(A[i][j] == 0)
{
points.push({i,j});
return ;
}
A[i][j] = 2;
//Continue depth traversal
dfs(A,points,m,n,i-1,j);
dfs(A,points,m,n,i+1,j);
dfs(A,points,m,n,i,j-1);
dfs(A,points,m,n,i,j+1);
return;
}
int shortestBridge(vector<vector<int>>& A) {
int m = A.size();
int n = A[0].size();
//Depth traversal to find the first island
int flag = 0;
queue<pair<int,int>> points;
for(int i = 0; i < m; i++)
{
if(flag == 1) break;
for(int j = 0; j < n; j++)
{
//Exit immediately after traversing an island in depth
if(A[i][j] == 1)
{
flag = 1;
dfs(A,points,m,n,i,j);
break;
}
}
}
int level = 0;
while(!points.empty())
{
int N = points.size();
level++;
while(N--)
{
auto [r,c] = points.front();
points.pop();
//Traverse around
for(int k = 0; k < 4; k++)
{
int x = r + direction[k];
int y = c + direction[k+1];
if(x >= 0 && x < m && y >= 0 && y < n)
{
//If it's still the first island
if(A[x][y] == 2) continue;
if(A[x][y] == 1) return level;
//If it is still 0, continue to queue
points.push({x,y});
//Merge this coordinate into the first island
A[x][y] = 2;
}
}
}
}
return level;
}
};
```

Keywords: Algorithm leetcode queue dfs bfs

Added by meltingpotclub on Fri, 11 Feb 2022 07:32:19 +0200