LeetCode—200.岛屿数量[Number of Islands]——分析及代码[C++]
一、题目
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、分析及代码
1. 深度优先搜索
(1)思路
对每一块发现的陆地,进行深度优先搜索,并在过程中将所发现的陆地记为 ‘0’。
则每次新发现陆地的次数即为所求岛屿数量(每次搜索陆地时,先前岛屿的陆地已被记为 ‘0’)。
(2)代码
class Solution {
int n, m, count;
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty())
return 0;
n = grid.size(), m = grid[0].size();
count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j] == '1') {
dfs(i, j, grid);
count++;
}
return count;
}
void dfs(int i, int j, vector<vector<char>>& grid) {
grid[i][j] = '0';
if (i < n - 1 && grid[i + 1][j] == '1')
dfs(i + 1, j, grid);
if (i > 0 && grid[i - 1][j] == '1')
dfs(i - 1, j, grid);
if (j < m - 1 && grid[i][j + 1] == '1')
dfs(i, j + 1, grid);
if (j > 0 && grid[i][j - 1] == '1')
dfs(i, j - 1, grid);
}
};
(3)结果
执行用时 :12 ms, 在所有 C++ 提交中击败了 92.41% 的用户;
内存消耗 :10.7 MB, 在所有 C++ 提交中击败了 91.81% 的用户。
三、其他
本题还可用广度优先搜索、并查集等方法求解,思路类似。