题目描述:
你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
思路:此题采用bfs算法,找到每个岛屿的最大连通块,看是否四周都有陆地,有的话就不会被淹没,而被标记过得点就不用再以它为起点寻找连通块了。
代码如下:
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1010; /定义像素规模
char mp[N][N]; /记录像素内容
int vis[N][N]; /标记数组,标记是否访问过该点
int flag; /如果四周全为陆地就设为1
int d[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; /四个方向
void bfs(int x, int y)
{
queue<pair<int, int>>q; /用stl的队列创建存储点(x,y)
q.push({ x,y }); /把坐标推进队列
vis[x][y] = 1; /访问过,设为1
while (q.size()) {
pair<int, int> t = q.front(); /取出第一个
q.pop(); /把取出的从队列中弹出来
int tx = t.first, ty = t.second;
if (mp[tx][ty + 1] == '#'&&mp[tx][ty - 1] == '#'&& /判断四周是否全为陆地
mp[tx + 1][ty] == '#'&&mp[tx - 1][ty] == '#')
flag = 1;
for (int i = 0; i < 4; i++) { /向四周延伸连续块
int nx = tx + d[i][0], ny = ty + d[i][1];
if (vis[nx][ny] == 0 && mp[nx][ny] == '#')
{
vis[nx][ny] = 1;
q.push({ nx,ny });
}
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> mp[i]; /坐标点输入
}
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (mp[i][j] == '#'&&vis[i][j] == 0) {
flag = 0; /用bfs函数找出连接块
bfs(i, j);
if (flag == 0) /flag为1代表全为陆地不会被湮没,为0就代表会被淹没,并计数
ans++;
}
}
}
cout << ans << endl;
return 0;
}