P2976 [USACO10JAN] Shipping Around an Island G
题意
在一个二维平面上，分布着水（
-
这条路线经过的每一个格子只能是水（
\texttt{.} ）。 -
这条环线路线的内部应包括整个大陆（
\texttt{A} ）。 -
这条环线路线的内部不应包括任一小岛（
\texttt{x} ）。
此外，我们规定这条路线可以多次经过同一个格子。也就是说，路线可以重叠。求这条路线的长度，即这条路线经过格子的个数（数据保证有解）。
例如下图，这条红色的路线是不合法的（路线内部包括了一个小岛
如下图，这条蓝色的路线是合法的（图中深蓝色表示路径重叠部分，阴影部分表示环线路线的内部）。
思路
染色
简而言之，这道题的本质就是染色。
染色在本题中体现为将一些水（
对于每一个水格子（
当
- 当格子
2 、4 、6 、8 中有大于等于三个格子是大陆（\texttt{A} ）时，直接将(i,j) 染色为\texttt{A} ，因为最短的路不可能走到这里。例如下图，格子2 、4 、6 为\texttt{A} ，因此格子5 也被染成\texttt{A} 。
- 当格子
2 、4 、6 、8 中恰好有两个格子是大陆（\texttt{A} ）时，且这两个\texttt{A} 分别位于格子5 的两侧，则这个格子暂时不填。例如下图，格子4 、6 为\texttt{A} 。若将格子5 填上，则格子1 、2 、3 向外延伸的水连通块与格子7 、8 向外延伸的水连通块有可能会被互相隔绝。
在下图的情况下，中间的格子是不能被填上的。因为如果填上了，会把里面的
在下图的情况下，中间的格子之后会被自下而上地重新搜到而填充上色，因为下面的格子之后会被染色。
因此，我们在将任一格子填充之后，必须重新判断这个格子周围一圈（八个）格子的情况并讨论其是否需要填充上色。
- 当格子
2 、4 、6 、8 中恰好有两个格子是大陆（\texttt{A} ）时，且这两个\texttt{A} 格子的顶点相邻（例如格子2 、4 或格子4 、8 ），则分以下两种情况讨论：
（1）当格子
需要注意的是，隔绝水格子的不只是大陆（
（2）当格子
这种类型的格子直接填上的原因是：填上之后只有好处没有坏处。如左下图，填上之后路径长度没有改变；如右下图，填上之后会导致右边两个粉色的格子之后也被填上，最终路径长度缩短。换句话说，填这种类型的格子对路径有截弯取直的作用。
- 当格子
2 、4 、6 、8 中只有小于等于一个格子是大陆（\texttt{A} ）时，这个格子暂时不填，同理，如有需要之后会重新搜回来。
按这种方式处理完所有格子之后，我们直接求一遍所得大陆的周长即可得出答案。
如下是样例染色前与染色后的对比。
...................
...................
.....A.............
.....A..x..........
..x..A.....AAAA....
.....A.....A..A....
.....AAAAAAAA.A....
........A.....A....
.xx...AAA...x.A....
......A............
...AAAAAAAAAAAAA...
................... ...................
...................
....AAA............
....AAA.x..........
..x.AAA...AAAAA....
....AAAAAAAAAAA....
....AAAAAAAAAAA....
....AAAAAAA...A....
.xx.AAAAAAA.x.A....
....AAAAAAA........
...AAAAAAAAAAAAA...
...................求大陆周长
我们采用常规思路：从第一次出现的大陆（
假设上一步的方向为向右，则这一步应优先向下，因为我们需要紧贴大陆走一圈；如果无法往下，则应尝试向右；如果还是不行，则应向上（我们规定第一步的上一步方向为向右）。
如下图，分别给出了当上一步（红色）为向右时，这一步（蓝色）分别向右、向上、向下时的情况。
同理，我们可得：若上一步的方向为
按此方法一直走，并记录经过的格子个数，直到走回起点。
代码实现 & 完整代码
由于这道题考察的主要是思维，且每个人的代码习惯不一，我会给出我的完整代码和注释，而不是每一步的具体实现方法。
#include<bits/stdc++.h>
#define int long long
#define maxn 1010
using namespace std;
int n,m,ans;
int d[10][2]={{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
int f[5][2]={{0,1},{1,0},{0,-1},{-1,0}};
char c[maxn][maxn];
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
return ret*f;
}
inline char GC(){
char ch=getchar();
while(ch!='.'&&ch!='A'&&ch!='x')ch=getchar();
return ch;
}
bool check(int x,int y){ // 判断一个点是否在地图范围之内
return (x>=1&&y>=1&&x<=n&&y<=m);
}
void color(int x,int y){ // 染色函数
if(c[x][y]!='.')return; // 若当前格子不是水，直接跳过
int cnt_A=0,cnt_x=0; // 统计该格子周围 A 的数量与 x 的数量
for(int i=0;i<=3;i++){
int xx=x+f[i][0],yy=y+f[i][1];
if(!check(xx,yy))continue;
cnt_A+=(c[xx][yy]=='A');
}
for(int i=0;i<=7;i++){
int xx=x+d[i][0],yy=y+d[i][1];
if(!check(xx,yy))continue;
cnt_x+=(c[xx][yy]=='x');
}
int chk=0;
for(int i=0;i<=3;i++){
if(c[x+f[i][0]][y+f[i][1]]=='A'&&c[x+f[(i+1)%4][0]][y+f[(i+1)%4][1]]=='A'&&c[x+f[(i+2)%4][0]][y+f[(i+2)%4][1]]=='.'&&c[x+f[(i+3)%4][0]][y+f[(i+3)%4][1]]=='.'){
// 情况 3.
chk=i+1;
break;
}
}
if((chk==1&&c[x-1][y-1]!='.')||(chk==2&&c[x-1][y+1]!='.')||(chk==3&&c[x+1][y+1]!='.')||(chk==4&&c[x+1][y-1]!='.'))chk=0;
// 情况 3.(1)
if((chk&&(!cnt_x))||cnt_A>=3){ // 情况 1. 或 3.(2)
c[x][y]='A';
for(int i=0;i<=7;i++){
int xx=x+d[i][0],yy=y+d[i][1];
if(!check(xx,yy))continue;
color(xx,yy); // 染色之后要重新判断周围格子的情况
}
}
// 情况 2. 与 4. 均不满足染色条件
}
void calc(int x,int y){ // 计算大陆周长
int nx=x,ny=y,opt=0; // opt 为上一步方向编号
do{
for(int i=5;i>=3;i--){ // 按优先级尝试走每一个方向（i 取 5 至 3 是为了避免下标出现负数）
int xx=nx+f[(opt+i)%4][0],yy=ny+f[(opt+i)%4][1];
if(c[xx][yy]=='.'){
nx=xx,ny=yy;
opt=(opt+i)%4; // 更新方向编号
break;
}
}
ans++; // 记录经过的格子总数
}while(!(nx==x&&ny==y));
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c[i][j]=GC();
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)color(i,j); // 尝试对每一个格子做染色操作
int chk=1;
for(int i=1;i<=n&&chk;i++){
for(int j=1;j<=m&&chk;j++){
if(c[i][j]=='A'){
calc(i-1,j); // 从第一次出现的 A 的上面一格开始计算大陆周长
chk=0;
}
}
}
printf("%lld\n",ans);
return 0;
}本文参考了题解1和题解2。但其年代久远，有些地方没有讲清楚。这篇题解给出了更清楚的解题思路。