[product understanding foundation DFS]

695. Maximum area of the island

1. This problem is equivalent to finding the largest sub block size in the connected sub block
2. You need to mark whether the grid has been accessed
3. The essence of using the direction array to cycle four times is the same as directly writing the following code. It depends on your personal preferences

// Basic DFS framework: search four adjacent squares at a time
void dfs(int[][] grid, int r, int c) {
    dfs(grid, r - 1, c); // Upper adjacent
    dfs(grid, r + 1, c); // Lower adjacent
    dfs(grid, r, c - 1); // Left adjacent
    dfs(grid, r, c + 1); // Right adjacent
}

/*Author: nettee
 Link: https://leetcode-cn.com/problems/max-area-of-island/solution/fang-ge-lei-dfs-de-jian-dan-fang-fa-cjava-by-nette/ */

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        if(m==0||n==0) return 0;
        int maxArea=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                    maxArea=max(maxArea,dfs(grid,i,j));
            }
        }
        return maxArea;
    }

    int dfs(vector<vector<int>>& grid,int x,int y)
    {
        if(grid[x][y]==0) return 0;
        grid[x][y]=0;//Equivalent to having visited
        int area=1;

        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(tx>=0&&tx<grid.size()&&ty>=0&&ty<grid[0].size())
            {
                area+=dfs(grid,tx,ty);
            }
        }

        return area;


    }
};

547. Number of provinces

1. This question is different from the connected representation of lattice DFS. Compared with the intuitive representation of lattice DFS, the representation of this question is obviously more implicit
2. You can also use and query sets. DFS is used here
3. It is equivalent to counting the number of connected sub blocks in a graph, so the visited points in the same connected block should be marked

class Solution {
public:
    bool vis[205]={false};//Indicates that it has not been accessed
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        int cnt=0;
        
        for(int i=0;i<n;i++)
        {
            if(vis[i]==false)
            {
                cnt++;
                dfs(isConnected,i);
            }
        }
        return cnt;
    }

    void dfs(vector<vector<int>>& isConnected,int k)
    {
        vis[k]=true;
        for(int i=0;i<isConnected.size();i++)
        {
            if(isConnected[k][i]==1&&vis[i]==false) dfs(isConnected,i);
        }
    }
};

417. Pacific Atlantic currents

1. If this problem traverses the whole graph, the overhead is very large, so we should use reverse thinking to traverse only the points on the edge
2. It is equivalent to finding all points connected to both sides in the graph and marking the vis array
3. Search from "water" to higher land, and you can get the answer
4. I forgot the c + + function pointer, so I put the rotten code below
5. If the point is True in vis1 and True in vis2, it meets the meaning of the question

class Solution {
public:

    bool vis1[160][160]={false};//Record the point where it can flow to the Pacific Ocean
    bool vis2[160][160]={false};//Record the point where it can flow to the Atlantic Ocean
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int n=heights.size();
        int m=heights[0].size();
        vector<vector<int>> res;
        for(int i=0;i<n;i++)
        {
            dfs1(heights,i,0);
            dfs2(heights,i,m-1);
        }

        for(int j=0;j<m;j++)
        {
            dfs1(heights,0,j);
            dfs2(heights,n-1,j);
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(vis1[i][j]&&vis2[i][j])
                {
                    res.push_back({i,j});
                }
            }
        }
        return res;



    }

    void dfs1(vector<vector<int>>& heights,int x,int y)
    {
        vis1[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(tx>=0&&tx<heights.size()&&ty>=0&&ty<heights[0].size()&&heights[tx][ty]>=heights[x][y]&&vis1[tx][ty]==false) dfs1(heights,tx,ty);
        }

    }

    void dfs2(vector<vector<int>>& heights,int x,int y)
    {
        vis2[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(tx>=0&&tx<heights.size()&&ty>=0&&ty<heights[0].size()&&heights[tx][ty]>=heights[x][y]&&vis2[tx][ty]==false) dfs2(heights,tx,ty);
        }

    }
};

[retrospective series]

NOTE: backtracking is often used to arrange, combine and select problems

46. Full arrangement

I did it in the most classic way... But it's not efficient.

1. For backtracking, the access array should be set to have been accessed before dfs. After the search, it should return to the original situation, that is, the unreached state
2. Set a path/track/temp array to put the selected points that meet the conditions into the; When the boundary condition is reached, the whole container output or is added to the result container. After backtracking, the last point pop will be added

class Solution {
public:
    vector<vector<int>> res;
    bool vis[15]={false};
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> temp;
        dfs(nums,0,temp);
        return res;


    }

    void dfs(vector<int>& nums,int index,vector<int> temp)
    {
        
        if(temp.size()==nums.size())
        {
       
            res.push_back(temp);
            return;
        }

        for(int i=0;i<nums.size();i++)
        {
           
            if(vis[i]==false)
            {
             temp.push_back(nums[i]);
             vis[i]=true;
             dfs(nums,i+1,temp);
             temp.pop_back();
             vis[i]=false;
            }
        }

    }
};

[pruning required]