全球变暖

[蓝桥杯 2018 省 AB] 全球变暖

题目描述

你有一张某海域NxN像素的照片，. 表示海洋、 # 表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

其中 “上下左右” 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数 $N$。(1<=n<=1000)。

以下 N行 N 列代表一张海域照片。

照片保证第 1 行、第 1列、第 N行、第 N列的像素都是海洋。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

7 
.......
.##....
.##....
....##.
..####.
...###.
.......

样例输出 #1

1

理解

用DFS深搜，也可以BFS广搜

代码

DFS

#include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>

using namespace std;

char s[1005][1005];
int n,ans,xx[]={1,-1,0,0},yy[]={0,0,1,-1};
bool v=1,vis[1005][1005];
bool good(int x,int y)
{
    return s[x][y]!='.';
}
bool dfs(int x,int y)
{
    vis[x][y]=1;
    if(good(x-1,y)&&good(x+1,y)&&good(x,y-1)&&good(x,y+1))
        v=0;
    for(int i=0;i<4;i++)
    {
        int X=x+xx[i],Y=y+yy[i];
        if(good(X,Y)&&vis[X][Y]==0)
            dfs(X,Y);
    }
    s[x][y]='.';
    return v;

}
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
		for(int j = 1;j<=n;j++)
			cin>>s[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(good(i,j))
            {
                v=1,ans+=dfs(i,j);
            }
        }
    }
    cout<<ans;
	return 0;
}

BFS

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define MAX 1010
using namespace std;
 
int n, ans=0,sign;
bool visited[MAX][MAX];
int nextt[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
char map[MAX][MAX];
 
bool check(int x, int y) {//如果存在不会被淹没的（x,y）就返回true，反之返回false
	for (int i = 0; i < 4; i++) {
		int tx = x + nextt[i][0];
		int ty = y + nextt[i][1];
		if (map[tx][ty] == '.') {
			return false;
		}
	}
	return true;
}
 
void bfs(int x, int y) {
	queue<pair<int, int> >q;
	q.push({ x,y });
	visited[x][y] = true;
 
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		if (check(x, y)) {
			sign = 1;
		}
		for (int k = 0; k < 4; k++) {
			int tx = x + nextt[k][0];
			int ty = y + nextt[k][1];
			if (map[tx][ty] == '.' || visited[tx][ty]) {
				continue;
			}
			visited[tx][ty] = true;
			q.push({ tx,ty });
		}
	}
}
 
 
int main()
{
	int num = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visited[i][j] && map[i][j] == '#') {
				num++;//原来的岛屿总数
				sign = 0;
				bfs(i, j);
				if (sign == 1) {
					ans++;//不会被淹没的岛屿数
				}
			}
		}
	}
	cout << num-ans << endl;
	return 0;
}