力扣-dfs

何为深度优先搜索算法？

深度优先搜索算法，即DFS。就是找一个点，往下搜索，搜索到尽头再折回，走下一个路口。

695.岛屿的最大面积

695. 岛屿的最大面积

题目

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

题解

就是进行左右上下的搜索，选择第一个位置，如果为1，即陆地，就对周进行搜索，被搜索到的地方置为0.并且设置一个最大陆地，每一次得到新的陆地面积就进行比较，取最大值。

为什么搜索到就置为0呢？因为如果是同一片，那么搜索第一个陆地的时候就会把这一片全部搜索了，所以没必要重复搜索，节约时间。
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max=0;
        int area=0;
        int i,j;
        for(i=0;i<grid.size();i++){
            for(j=0;j<grid[0].size();j++){
                if(grid[i][j]==1){
                    area=findArea(grid,i,j);
                    if(area>max)
                        max=area;
                }
            }
        }
        return max;
    }
    int findArea(vector<vector<int>>& grid,int i,int j){
        if(i==grid.size()||i<0)
            return 0;
        else if(j==grid[0].size()||j<0)
            return 0;
        if(grid[i][j]==1){
            grid[i][j]=0;
            return 1+findArea(grid,i+1,j)+findArea(grid,i-1,j)+findArea(grid,i,j+1)+findArea(grid,i,j-1);
        }
        return 0;
    }
};

547.省份数量

547. 省份数量

题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

题解

等于1就是二者相连。可以先设置一个visit数组来记录改行是否已经被遍历过了，避免重复计数。

一行一行遍历，如果没有访问过，则判断是否为0，不是则进行寻找。寻找的时候访问改行，并且对改行（即该节点）连接的也一起访问了。（这里递归解决）

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size(),count=0;
        vector<bool> visit(n,false);
        int i;
        for(i=0;i<n;i++){
            if(!visit[i]){
                find(isConnected,visit,i);
                count++;
            }
        }
        return count;
    }
    void find(vector<vector<int>>& isConnected,vector<bool>& visit,int i){
       visit[i]=true;
       int j;
       for(j=0;j<isConnected.size();j++){
        if(!visit[j]&&isConnected[i][j]==1){
            find(isConnected,visit,j);
        }
       }
    }
};

417.太平洋大西洋水流问题

417. 太平洋大西洋水流问题

题目

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：
输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <=

题解

水往低处流。如果一个一个点判断会比较麻烦，我们不妨换一种思路，从四条边出发。因为四边是确认可以流入其中一个海的。四条边开始进行dfs。

反向思考，即水从高处来。分别设置两个标记函数标记是否可以流入某一个海。当两个标记函数都显示true，则代表该位置的水可以流入两个海。

find函数部分实现dfs。定义一个dirs，分别是前后左右四个方向。在每一个位置的时候进行判断，如果不是边界且大于0，并且下一步大于该位置，证明该位置是可以流的。然后往下一步走，一直遍历。

主函数则是定义两个函数分别从四条边出发一个记录可以流入太平洋，一个记录可以流入大西洋。二者都是true即该位置可以流入对应的海洋。
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        if(heights.size()==0||heights[0].size()==0)
            return {};
        const int m=heights.size();
        const int n=heights[0].size();
        vector<vector<bool>> p_visit(m,vector<bool>(n,false));
        vector<vector<bool>> a_visit(m,vector<bool>(n,false));
        int i,j;
        for(i=0;i<m;i++){
            find(heights,p_visit,i,0);
            find(heights,a_visit,i,n-1);
        }
        for(j=0;j<n;j++){
            find(heights,p_visit,0,j);
            find(heights,a_visit,m-1,j);
        }
        vector<vector<int>> ans;
        for(i=0;i<m;i++){
            for(j=0;j<n;j++){
                if(p_visit[i][j]&&a_visit[i][j])
                    ans.push_back({i,j});
            }
        }
        return ans;
    }
    void find(vector<vector<int>>& heights,vector<vector<bool>>& visit,int i,int j){
        int m=heights.size();
        int n=heights[0].size();
        visit[i][j]=true;
        vector<pair<int,int>> dirs={{0,1},{0,-1},{1,0},{-1,0}};
        for(auto d:dirs){
            int nx=i+d.first;
            int ny=j+d.second;
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&!visit[nx][ny]&&heights[nx][ny]>=heights[i][j])
                find(heights,visit,nx,ny);
        }
    }
};