标题：全球变暖
【题目描述】
你有一张某海域NxN像素的照片，”.”表示海洋、”#”表示陆地，如下所示：…….
.##….
.##….
….##.
..####.
…###.
…….其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…….
…….
…….
…….
….#..
…….
…….请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。【样例输入】
7
…….
.##….
.##….
….##.
..####.
…###.
…….【样例输出】
1资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。提交程序时，注意选择所期望的语言类型和编译器类型。
//21:10 21:20 思路出 10
//23:20 23:35 15
//7:45 8:05 20
#include<bits/stdc++.h>
using namespace std;
int N;
bool vis[1005][1005];
char a[1005][1005];
char b[1005][1005];
bool v[1005][1005];
void dfs(int i,int j)
{
if(i<2||i>N-1||j<2||j>N-1||a[i][j]=='.')//||vis[i][j]
{
return ;
}
if(a[i][j]=='#')
{
// vis[i][j]=true;
a[i][j]='.';
}
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j+1);
dfs(i,j-1);
}
void dfs2(int i,int j)
{
if(i<2||i>N-1||j<2||j>N-1||b[i][j]=='.')//||vis[i][j]
{
return ;
}
if(b[i][j]=='#')
{
// vis[i][j]=true;
b[i][j]='.';
}
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j+1);
dfs(i,j-1);
}
void change()
{
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(b[i-1][j]=='.'||b[i+1][j]=='.'||b[i][j-1]=='.'||b[i][j+1]=='.')
v[i][j]=true;
}
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
if(v[i][j])
b[i][j]='.';
}
}
}
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin>>a[i][j];
b[i][j]=a[i][j];
}
}
int ans=0,ans2=0;
for(int i=1;i<=N;i++)//运用dfs计算陆地的数量
{
for(int j=1;j<=N;j++)
{
if(a[i][j]=='#')
{
dfs(i,j);
ans++;
}
}
}
change();
for(int i=1;i<=N;i++)//运用dfs计算陆地的数量
{
for(int j=1;j<=N;j++)
{
if(b[i][j]=='#')
{
dfs2(i,j);
ans2++;
}
}
}
cout<<ans-ans2<<endl;
return 0;
} #include <iostream>
#include <string>
using namespace std;
int n, m, cnt=0;
string maze[110];
bool vis[110][110];
void dfs(int x,int y)
{
if(x<0||x>=n||y<0||y>=m||vis[x][y]||maze[x][y]=='.')
{
return;
}
vis[x][y]=true;
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> maze[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (maze[i][j] == '#'&&!vis[i][j])
{
dfs(i,j);
cnt++;
}
}
}
cout<<cnt<<endl;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/92915.html
