题解 P7645
追梦之鲸
·
·
题解
经典回顾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
```c
...
.X.
.X.
.X.
...
```
现在我们按上面那段话来把 $S$ 转换成 $M$。
$M$ 矩阵：
```c
989
838
828
838
989
```
我们来看看 $M$ 矩阵的变化：
```c
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：
```c
//本人码风可能有问题，请见谅
#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;
}
```