题目描述
给你一个由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.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] 的值为 ‘0’ 或 ‘1’
算法1
BFS
时间复杂度
参考文献
C++ 代码
(用数组模拟的队列,没有用stl)
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m; // n行,每行m个数
int grid[N][N]; // 二维网格
int result; // 岛屿的个数
PII queue[N * N];
int bfs()
{
int hh = 0, tt = 0; // 队头hh,队尾tt
// 向上、向下、向左、向右四个方向的向量
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++) // 遍历网格
{
if (grid[i][j] == 1) // 如果当前位置grid[i][j]为陆地
{
result += 1; // 岛屿的个数加一
grid[i][j] = 0; // 同时将(i,j)处值置零,以表示该处搜索过了
queue[ ++ tt] = {i, j}; //将(i,j)入队
while (hh <= tt) // 只要队列不空
{
auto t = queue[hh ++]; // 取出队头元素
// 去扫描队头元素的上、下、左、右四个方向上是否还有陆地,即grid[x][y]是否为1
for (int i = 0; i < 4; i ++)
{
int x = t.first + dx[i], y = t.second + dy[i]; // 向量表示法
if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) // 如果在网格内,且所到之处为陆地
{
grid[x][y] = 0; // 将该处置零
queue[ ++ tt] = {x, y}; // 同时将这个位置入队
}
}
}
}
}
return result;
}
int main()
{
// 先把地图读进来
cin >> n >> m;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j++)
cin >> grid[i][j];
// 直接输出bfs()
cout << bfs() << endl;
return 0;
}
算法2
DFS
blablabla
时间复杂度
参考文献
C++ 代码
blablabla