「算法刷题」深度优先遍历之岛屿问题

[TOC]

岛屿系列算法问题是经典的面试高频题，岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。如何在二维矩阵中使用 DFS 搜索呢？

我们可以把二维矩阵中的每个点看做一个节点，这个节点的上下左右四个位置就是相邻节点，那么整个矩阵就可以抽象成一幅网状的「图」结构，二维矩阵的搜索问题就变成了从某个点出发，向上下左右四个方向进行深度搜索的问题，该dfs函数的框架如下：

// 从(i, j)出发，向相邻四个方向搜索
void dfs(vector<vector<int>>& grid,int i,int j, vector<vector<bool>>& visited) {
    int m = grid.length, n = grid[0].length;
    // 如果超出索引边界，返回
    if (i < 0 || j < 0 || i >= m || j >= n) return;
    // 如果已遍历过 (i, j)，返回
    if (visited[i][j]) return;
    // 进入节点 (i, j)
    visited[i][j] = true;// 标记当前点已经访问过
    dfs(grid, i - 1, j, visited); // 向上搜索
    dfs(grid, i + 1, j, visited); // 向下搜索
    dfs(grid, i, j - 1, visited); // 向左搜索
    dfs(grid, i, j + 1, visited); // 向右搜索
}

该dfs函数有一个 visited 布尔数组的参数，其目的是防止走回头路，在不同的问题中可以灵活变换，这里放入模板是告诉你二维矩阵需要有一个标记来防止走回头路。

1、求岛屿的数量

200. 岛屿数量（中等难度）

输入一个二维网格grid，其中’1’表示陆地，’0’表示水域，整个网格被水完全包围，陆地格子水平和垂直方向相连（对角线方向不相连）则形成一个岛屿。

点评：

在下述写法中，dfs 函数遍历到值为 '0' 的位置会直接返回，而且搜索一个岛屿后就不会再遍历该岛屿中的”1”，所以我们可以直接省略visited数组，只要把经过的位置都设置为 '0'，就可以起到不走回头路的作用。

注意该题目中是个字符矩阵。

class Solution {
public:
    /* 深度优先遍历：
    二维遍历每个点，如果当前点是陆地就深度遍历
    每个点都以上下左右的方式去做深度递归，搜索过的方格都需要做标记，
    */
    int m;
    int n;
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(); 
        n = grid[0].size();
        // 遍历二维数组中的每个点
        int res=0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j <n; j++){
                // 如果当前点是陆地，就判断是否形成岛屿（该条件可以删除，但是影响效率）
                if(grid[i][j] == '1'){
                    dfs(grid,i,j);//一定会形成一个岛屿，搜索后就淹没了
                    res++;
                }
            }
        }
        return res;
    }
    // 从[i,j]向四周搜索，将搜索过的1标记为其他值（0,淹没）
    void dfs(vector<vector<char>>& grid,int i,int j){
        // 如果当前点超出范围
        if(i<0||i>=m||j<0||j>=n) return ;
        // 如果当前点是湖水
        if(grid[i][j]=='0') return ;
        // 如果当前点已遍历过
        if(grid[i][j]=='2') return ;
        grid[i][j]='2';// 遍历过就标记为2,只要不标记为1（陆地）就行
        // 向四周遍历
        dfs(grid,i-1,j);// 向左遍历
        dfs(grid,i+1,j);// 向右遍历
        dfs(grid,i,j-1);// 向上遍历
        dfs(grid,i,j+1);// 向下遍历
    }
};

1254. 统计封闭岛屿的数目（中等难度）

输入一个二维网格grid，其中0表示陆地，1表示水域，陆地格子水平和垂直方向相连（对角线方向不相连）则形成一个岛屿，封闭岛屿则是其四周完全被水包围。

点评：

该题目中没有假定二维矩阵四周是被海水包围的，所以「靠边的岛屿」理论上可能就不是「封闭岛屿」。

所以在dfs 函数中将「靠边的岛屿」标记下，这样统计的岛屿个数中去除「靠边的岛屿」就是「封闭岛屿」的个数。

class Solution {
public:
    /* 该题用0表示土地，1表示水（和其他岛屿问题不同）
    所有的岛屿可以分为封闭岛屿和非封闭岛屿，我们已知如何求所有岛屿数量（200题）
    封闭岛屿的特点是接触到了边界，所以只要判断当前统计的岛屿是不是封闭岛屿即可
    */
    int m;
    int n;
    int closedIsland(vector<vector<int>>& grid) {
        m = grid.size(); 
        n = grid[0].size();
        // 遍历二维数组中的每个点
        int res=0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j <n; j++){
                // 如果当前点是陆地，就扩散
                if(grid[i][j] == 0){
                    bool isClosed=false;
                    dfs(grid,i,j,isClosed) ;
                    if(!isClosed) res++;
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& grid,int i,int j,bool& isClosed){
        // 如果当前点超出范围就返回
        if(i<0||i>=m||j<0||j>=n) {
            isClosed=true;
            return ;
        }
        // 如果当前点不是陆地就返回
        if(grid[i][j]==1) return ;
        // 如果当前点遍历过就返回
        if(grid[i][j]==2) return ;
        grid[i][j]=2;// 遍历过就标记为2
        // 向四周遍历
        dfs(grid,i-1,j,isClosed);// 向左遍历
        dfs(grid,i+1,j,isClosed);// 向右遍历
        dfs(grid,i,j-1,isClosed);// 向上遍历
        dfs(grid,i,j+1,isClosed);// 向下遍历
    }
};

1905. 统计子岛屿（中等难度）

点评：

这道题的关键在于，如何快速判断子岛屿？

什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？

当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。

反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。

那么只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。

依据这个思路，可以直接写出下面的代码：

class Solution {
public:
    /*当岛屿B中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
    反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，
    那么岛屿 B就不是岛屿A的子岛*/
    int m;
    int n;
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        m = grid1.size(); 
        n = grid1[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j <n; j++){
                // 如果岛屿A中陆地在岛屿B中是海水，就淹掉这座小岛
                if(grid1[i][j]==0&&grid2[i][j]==1)
                    dfs(grid2,i,j);//淹掉这座小岛
            }
        }
        // 遍历二维数组中的每个点
        int res=0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j <n; j++){
                // 如果当前点是陆地，就判断
                if(grid2[i][j] == 1){
                    dfs(grid2,i,j);
                    res++;
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& grid,int i,int j){
        // 如果当前点超出范围
        if(i<0||i>=m||j<0||j>=n) return ;
        // 如果当前点是湖水
        if(grid[i][j]!=1) return ;
        // 如果当前点已遍历过
        if(grid[i][j]==0) return ;
        grid[i][j]=0;// 遍历过就标记为0
        // 向四周遍历
        dfs(grid,i-1,j);// 向左遍历
        dfs(grid,i+1,j);// 向右遍历
        dfs(grid,i,j-1);// 向上遍历
        dfs(grid,i,j+1);// 向下遍历
    }
};

694. 不同岛屿的数量（中等难度）

点评：

我们已经会统计矩阵中所有岛屿的数量，也会统计其中「封闭岛屿」的数量，该题是求其中「不同岛屿」的数量。那么如何区分「不同岛屿」？

该题目中的意思是两个岛屿的节点的拓扑结构一样就是相同岛屿（可以直接平移得到），否则就是「不同岛屿」。那么如何表示一个岛屿的拓扑结构呢？这和岛屿的遍历顺序有关。

简单点说，从grid[i][j]出发向四周搜索时，不同的结构在不同的时机返回的顺序不一样，有的结构可能向上搜索一次就直接返回，向下搜索多次才能返回。对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的。

我们可以为dfs函数输入一个字符串参数，其每次向四个方向搜索一次就添加一个不同的字符，这样相同结构的岛屿就会得到一条相同的字符串，否则就是不同的字符串。

将每个岛屿搜索后的字符串放入哈希集合中，哈希集合自动帮我们去重，然后返回哈希集合的大小即可。

class Solution {
public:
    int m; // 行数
    int n; // 列数
    int numDistinctIslands(vector<vector<int>>& grid) {
        m = grid.size(); 
        n = grid[0].size();
        unordered_set<string> set;// 使用哈希集合来存储字符串
        // 遍历二维数组中的每个点
        for(int i = 0; i < m; i++){
            for(int j = 0; j <n; j++){
                // 如果当前点是陆地，就扩散
                if(grid[i][j] == 1){
                    string str = "";
                    dfs(grid,i,j,str);
                    set.insert(str);
                }
            }
        }
        return set.size();
    }
    void dfs(vector<vector<int>>& grid,int i,int j,string& str){
        // 如果当前点超出范围就返回
        if(i<0||i>=m||j<0||j>=n)return;
        // 如果当前点不是陆地就返回
        if(grid[i][j]==0)return;
        grid[i][j]=0;// 遍历过就标记为2
        // 向四周遍历
        dfs(grid,i-1,j,str);// 向左遍历
        str += '1';
        dfs(grid,i+1,j,str);// 向右遍历
        str += '2';
        dfs(grid,i,j-1,str);// 向上遍历
        str += '3';
        dfs(grid,i,j+1,str);// 向下遍历
        str += '4';
    }
};

2、求岛屿的周长

463. 岛屿的周长（简单难度）

点评：

设计dfs函数从[i,j]出发向四周遍历，返回四个方向边界和湖水的个数，那么就可以得到一个岛屿的周长。

本题的题意是矩阵中始终只会有一个岛屿，我们的代码求的是所有岛屿的周长之和，更进一步：

class Solution {
public:
    /* 该题中没有岛内湖，则所有的边长只有两种可能：边界或者湖*/
    int m;
    int n;
    int islandPerimeter(vector<vector<int>>& grid) {
        m = grid.size(); 
        n = grid[0].size();
        int res=0;
        // 遍历二维数组中的每个点
        for(int i = 0; i < m; i++){
            for(int j = 0; j <n; j++){
                // 如果当前点是陆地，就扩散
                if(grid[i][j] == 1){
                    res+=dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    // 从[i,j]出发向四周遍历，返回四个方向边界和湖水的个数
    int dfs(vector<vector<int>>& grid,int i,int j){
        // 如果当前点超出范围,可做周长
        if(i<0||i>=m||j<0||j>=n) return 1;
        // 如果当前点是湖水，可做周长
        if(grid[i][j]==0) return 1;
        // 如果当前点已遍历过，不可做周长
        if(grid[i][j]==2) return 0;
        grid[i][j]=2;// 遍历过就标记为2
        // 向四周遍历
        int res=0;
        res+=dfs(grid,i-1,j);// 向左遍历
        res+=dfs(grid,i+1,j);// 向右遍历
        res+=dfs(grid,i,j-1);// 向上遍历
        res+=dfs(grid,i,j+1);// 向下遍历
        return res;
    }
};

3、求岛屿的面积

695. 岛屿的最大面积（中等难度）

剑指 Offer II 105. 岛屿的最大面积（中等难度）

点评：

该题目求所有岛屿的最大面积，我们可以用dfs函数求出一个岛屿的面积，最后保存下面积最大的数即可。

改造dfs函数使其返回一个整型面积，显然在grid[i][j]的面积=向上下左右搜索的面积之和+1

注意该题目中的矩阵最大为50阶。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int res = 0;
        // 遍历二维数组中的每个点
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j <grid[0].size(); j++){
                // 如果当前点是陆地，就扩散
                if(grid[i][j] == 1){
                    res=max(res,dfs(grid,i,j));//记录每个点遍历的面积的最大值
                }
            }
        }
        return res;
    }
    // 搜索[i,j]向四周扩散后能获得的最大面积
    int dfs(vector<vector<int>>& grid,int i,int j){
        // 如果当前点超出范围就返回
        if(i<0||i>=grid.size()||j<0||j>=grid[0].size()) return 0;
        // 如果当前点不是陆地就返回
        if(grid[i][j]!=1)return 0;
        // 如果当前点已经遍历过,直接返回
        if(grid[i][j]==-1)return 0;
        grid[i][j]=-1;// 遍历过就标记为-1
        // 向四周遍历
        int size =1;
        size+=dfs(grid,i-1,j);// 向左遍历
        size+=dfs(grid,i+1,j);// 向右遍历
        size+=dfs(grid,i,j-1);// 向上遍历
        size+=dfs(grid,i,j+1);// 向下遍历
        return size;
    }
};

1020. 飞地的数量（中等难度）

点评：

该题目和「 1254.统计封闭岛屿的数目」非常相似，这题不求封闭岛屿的数量，而是求封闭岛屿的面积总和。

注意该题中 1 代表陆地，0 代表海水。

class Solution {
public:
    /*简单讲，本题就是求解所有封闭岛屿的面积，靠近边界的岛屿就不是封闭岛屿*/
    int m;
    int n;
    int numEnclaves(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        // 遍历二维数组中的每个点
        int res=0;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                bool isClosed=false;
                int size=dfs(grid,i,j,isClosed);// 如果是非封闭岛屿则
                if(!isClosed) res+=size;
            }
        }
        return res;
    }
    int dfs(vector<vector<int>>& grid,int i,int j,bool& isClosed){
        if(i<0||i>=m||j<0||j>=n){
            isClosed=true;
            return 0;
        }
        if(grid[i][j]==0) return 0;
        grid[i][j]=0;
        int size=1;
        size+=dfs(grid,i-1,j,isClosed);
        size+=dfs(grid,i+1,j,isClosed);
        size+=dfs(grid,i,j-1,isClosed);
        size+=dfs(grid,i,j+1,isClosed);
        return size;
    }
};

4、求矩阵的最长递增路径

329. 矩阵中的最长递增路径（困难难度）

剑指 Offer II 112. 最长递增路径（困难难度）

点评：

该题目求矩阵的最长递增路径，我们可以用dfs函数求出从matrix[i][j]出发向四个方向搜索的最大连续递增长度，显然该长度是四个方向结果的最大值+1。

注意该题目中的矩阵最大为200阶，其题目计算量较大，容易超时，所以我们需要加入一个记忆化搜索，

简单说，我们的visited数组直接保存在matrix[i][j]的最长递增路径，这样面对相同的点就不会重复搜索

class Solution {
public:
    /* 从一个格子开始向上下左右搜索，如果四周存在小于它的，遍历过需要标记
    那么其最大连续递增长度即为周围小于它的格子的最大连续递增长度中的最大值+1
    */
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int res = 0;
        vector<vector<int>> visited = vector< vector<int> > (matrix.size(), vector <int> (matrix[0].size()));
        // 遍历二维数组中的每个点
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j <matrix[0].size(); j++){
                // 如果当前点没有遍历过
                if(visited[i][j]==0){
                    res=max(res,dfs(matrix,i,j,-1,visited));
                }
            }
        }
        return res;
    }
     int dfs(vector<vector<int>>& matrix,int i,int j,int last,vector<vector<int>>& visited){
        // 如果当前点超出范围就返回
        if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size()) return 0;
        // 如果当前点比上一个点小就返回
        if(matrix[i][j]<=last)return 0;
        // 如果当前点已经计算过，就直接返回最大路径
        if(visited[i][j] != 0) return visited[i][j];
        // 向四周遍历,取最大方向
        int size =0;
        int tmp=matrix[i][j];
        size=max(size,dfs(matrix,i-1,j,tmp,visited));// 向左遍历
        size=max(size,dfs(matrix,i+1,j,tmp,visited));// 向右遍历
        size=max(size,dfs(matrix,i,j-1,tmp,visited));// 向上遍历
        size=max(size,dfs(matrix,i,j+1,tmp,visited));// 向下遍历
        // 标记当前点已经遍历过
        visited[i][j]=size+1;
        return visited[i][j];
    }
};

5、在矩阵中匹配字符串

79. 单词搜索（中等难度）

剑指 Offer 12. 矩阵中的路径（中等难度）

点评：

该题目求字符矩阵中是否存在一个字符串，我们可以用dfs函数求出从board[i][j]出发向四个方向搜索如果有一个方向匹配即可，显然dfs函数要传入字符串word和它的当前匹配索引k。

注意本题中求一个点board[i][j]后需要回溯，因为其遍历过的点之后可能还需要遍历

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        // 遍历二维数组中的每个点
        for(int i=0;i<board.size();++i){
            for(int j=0;j<board[0].size();++j){
                // 如果当前点满足测试条件
                if(board[i][j]==word[0]){
                    // 遍历测试
                    if(dfs(board,word,i,j,0)) return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board,string& word,int i,int j,int k){
        // 如果当前点超出范围
        if(k==word.size()) return true;
        // 如果当前点超出范围
        if(i<0||i>=board.size()||j<0||j>=board[0].size()) return false;
        // 如果当前点不匹配字符
        if(board[i][j]!=word[k]) return false;
        // 进入
        char tmp=board[i][j];
        board[i][j]='0';// 遍历过就标记为0
        // 向四周遍历
        bool res=dfs(board,word,i-1,j,k+1)||// 向左遍历
        dfs(board,word,i+1,j,k+1)||// 向右遍历
        dfs(board,word,i,j-1,k+1)||// 向上遍历
        dfs(board,word,i,j+1,k+1);// 向下遍历
        // 回溯
        board[i][j]=tmp;// 下一个点还可以遍历
        return res;
    }
};