Number of Islands

发表于 | 分类于

Number of Islands

题目描述：

给定一个矩阵，其中1表示陆地，0表示水；要求找到矩阵中岛的数量。

例子：

具体描述见LeetCode200

解题思路：

本题中主要用的方法是深度优先搜索；我们对矩阵中的每个位置进行遍历，如果是1的情况下，我们先将岛的数量加1，然后遍历整个岛的所有位置将其标记为0避免重复查找。这样我们就能找到全部的岛的数量。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++){
            for (int j = 0; j < grid[0].size(); j++){
                if (grid[i][j] == '1') count++;
                helper(grid, i, j);
            }
        }
        return count;
        
    }
    void helper(vector<vector<char>>& grid, int i, int j){
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
        if (grid[i][j] == '0') return;
        else {
            grid[i][j] = '0';
            helper(grid, i + 1, j);
            helper(grid, i, j + 1);
            helper(grid, i - 1, j);
            helper(grid, i, j - 1);
        }
    }
};