自动搬运

查看原文

来自洛谷，原作者为

	追梦之鲸 哼~

搬运于2025-08-24 22:31:50，当前版本为作者最后更新于2021-07-13 09:35:14，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

经典回顾P7645

思路

我们可以把这个 $R \times C$ 的字符矩阵 $S$ 化成一个 $R \times C$ 的数字矩阵 $M$ 来表示海岸线，这个 $M$ 矩阵中大于二的地方就是海，否则就是陆地。

我们先把 $M$ 矩阵里的数都变成零，也就是都是陆地。如果 $S_{i,j}$ 等于 . 那么就把 $M_{i,j}$ 变成等于一个大于三的数（因为这个地方的数大于三就表示这个地方要变成海，那这个地方原来是不是海就没关系了），我选的是五，然后把 $M_{i-1,j}\ M_{i+1,j}\ M_{i,j-1}\ M_{i,j+1}$ 都加一（海岸线嘛）。注：根据样例，地图外面都是海，所以要把地图里边的周围那一圈都加一，当然四个角上要加二。

好，现在我们来看一下样例，来加深一下对上面那段话的理解。

样例 #1

$S$ 矩阵：

...
.X.
.X.
.X.
...

现在我们按上面那段话来把 $S$ 转换成 $M$。

$M$ 矩阵：

989
838
828
838
989

我们来看看 $M$ 矩阵的变化：

5+4 5+3 5+4
5+3 0+3 5+3
5+3 0+2 5+3
5+3 0+3 5+3
5+4 5+3 5+4

如果还不懂可以自己推一下。

Code：

//本人码风可能有问题，请见谅
#include<bits/stdc++.h>
#define ri register
using namespace std;
template <class O>
inline void read(O &x) {ri char c = getchar();x=0;for (; !isdigit(c); c = getchar());for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);return;}
const int MAX=1e+9;
int fx[6]={1,-1,0,0};
int fy[6]={0,0,1,-1};
char ch;
int n,m,mp[12][12],a=MAX,b=MAX,c,d;
int main(){
	read(n);read(m);
	for(ri int i=1;i<=n;i++)
		for(ri int j=1;j<=m;j++){
			cin>>ch;
			if(ch=='.'){
				mp[i][j]=5;
				for(ri int k=0;k<4;k++)
					mp[i+fx[k]][j+fy[k]]++;
			}
		}
	for(ri int i=1;i<=n;i++)
		{mp[i][m]++;mp[i][1]++;}
	for(ri int i=1;i<=m;i++)
		{mp[n][i]++;mp[1][i]++;}
	for(ri int i=1;i<=n;i++)
		for(ri int j=1;j<=m;j++)
			if(mp[i][j]<3){
				a=min(a,i);
				b=min(b,j);
				c=max(c,i);
				d=max(d,j);
			}
	for(ri int i=a;i<=c;i++){
		for(ri int j=b;j<=d;j++){
			printf("%c",mp[i][j]<3?'X':'.');
		}
		printf("\n");
	}
	return 0;
}