题目
你有一张某海域 像素的照片,”.”表示海洋、”#”表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿,例如上图就有 座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数N。
以下 行 列,包含一个由字符”#”和”.”构成的 字符矩阵,代表一张海域照片,”#”表示陆地,”.”表示海洋。
照片保证第 行、第 列、第 行、第 列的像素都是海洋。
输出格式
一个整数表示答案。
数据范围
输入样例1:
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1:
1
输入样例2:
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2:
1
解题
方法一:BFS
思路
遍历+宽搜。
代码
#include <iostream>
#include <limits>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n;
char g[N][N];
int bfs(int x, int y) {
int flag = false;
queue<PII> que;
que.push({x, y});
g[x][y] = '*';
while (!que.empty()) {
auto pr = que.front();
que.pop();
x = pr.first, y = pr.second;
bool disappear = false;
for (auto& DIR : DIRS) {
int nx = x + DIR[0], ny = y + DIR[1];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (g[nx][ny] == '.') disappear = true;
if (g[nx][ny] == '#') {
que.push({nx, ny});
g[nx][ny] = '*';
}
}
if (!disappear) flag = true;
}
return !flag;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
cin.ignore(numeric_limits<streamsize>::max(), '\n');
for (int j = 0; j < n; ++j) {
scanf("%c", &g[i][j]);
}
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (g[i][j] == '#') cnt += bfs(i, j);
}
}
printf("%d\n", cnt);
return 0;
}
评论区