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;
        //Spread in four directions
        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;
			//Add cur adjacent nodes to the queue
			for(Node x: cur.adj())
			{
				//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
        set<string> deads;
        for(string s : deadends) deads.insert(s);
        //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
                if(deads.find(cur) != deads.end()) continue; 
                //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;
                }
            }
        }
        //Start breadth traversal
        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;
    }
};