自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 22:41:12，当前版本为作者最后更新于2023-04-02 16:34:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

upd:改进码风，更改错别字。

题目传送门

引言：

这个蒟蒻竟然交了几次才过，写个题解纪念一下。

题意

给出一张某海域 $N \times N$ 像素的照片，求有多少岛屿会被完全淹没。

思路

用 DFS 求出最开始有几个小岛，再求被海水淹没后还剩几个小岛，相减即可得到答案。

注意：被海水淹没后的陆地应用另一个字符表示，而不是把它变为海洋，这个点可以遍历，但不能被当作起点，不然就只有 $36$ 分。

例如：

9
.........
.#######.
.#######.
.#######.
..#.#....
.#######.
.#######.
.#######.
.........

如果你把被淹没的陆地改为海洋的话，后面求就会认为这是两个小岛，答案就会为 $-1$，但答案其实是 $0$。

code

#include<bits/stdc++.h>
using namespace std;
int n,ans,ans1;
int fx[6]={-1,0,1,0};
int fy[6]={0,1,0,-1};//方向数组
char d[1010][1010],f[1010][1010]; 
void dfs(int x,int y) //求淹没后有几个大陆 
{
	d[x][y] = '.';
	for(int i = 0;i < 4;i++) 
	{
		int xt = x + fx[i],yt = y + fy[i];
		if(d[xt][yt] != '.' && xt > 0 && xt <= n && yt > 0 && yt <= n) dfs(xt,yt);
	}
	return;
}
void df(int x,int y)//求淹没前有几个大陆 
{
	f[x][y] = '.';
	for(int i = 0;i < 4;i++) 
	{
		int xt = x + fx[i],yt = y + fy[i];
		if(f[xt][yt] == '#' && xt > 0 && xt <= n && yt > 0 && yt <= n) df(xt,yt);
	}
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			cin >> d[i][j],f[i][j] = d[i][j];
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++) 
			if(d[i][j] == '#' && (d[i-1][j] == '.' || d[i+1][j] == '.' || d[i][j-1] == '.' || d[i][j+1] == '.')) 
				d[i][j] = '-'; 
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			if(f[i][j] == '#')
			{
				ans1++;
				df(i,j);
			}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			if(d[i][j] == '#')
			{
				ans++;
				dfs(i,j);
			}
	printf("%d",ans1 - ans);
	return 0;
}