200. 岛屿数量
一句话套路网格 DFS 洪水填充沉岛
题目描述
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
示例 1:
输入:grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出:1
示例 2:
输入:grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出:3
提示:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
思路
时间
O(mn)空间
O(mn)(最坏递归栈)思路
扫到 '1' 就 ans++ 并把整座岛 DFS 沉成 '0'(洪水填充)。
沉岛 = visited 标记,避免同一座岛被重复计数。
延伸
不允许改原数组就另开 visited;要「动态加陆地后实时岛屿数」用并查集(Q305)。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0200 {
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
for (int i = 0; i < (int)grid.size(); ++i)
for (int j = 0; j < (int)grid[0].size(); ++j)
if (grid[i][j] == '1') {
++ans;
sink(grid, i, j);
}
return ans;
}
private:
static void sink(vector<vector<char>>& g, int i, int j) {
if (i < 0 || j < 0 || i >= (int)g.size() || j >= (int)g[0].size() || g[i][j] != '1') return;
g[i][j] = '0'; // 先标记再展开,防止来回递归
sink(g, i + 1, j);
sink(g, i - 1, j);
sink(g, i, j + 1);
sink(g, i, j - 1);
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0200::Solution s;
vector<vector<char>> a{{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '0', '0'}};
CHECK_EQ(s.numIslands(a), 1);
vector<vector<char>> b{{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}};
CHECK_EQ(s.numIslands(b), 3);
vector<vector<char>> c{{'0'}};
CHECK_EQ(s.numIslands(c), 0);