题目大意
题解
这种类型的题以前做过好多次了，但这题打了我一个考场的时间，但因为看错了题还是错了。
我的做法很简单，可以发现对于一个树林，可以在树林上找到一个横坐标最大的点。
然后分别将这个点的右上方的点和其下面的点，左上方的点和其下面的点遮住，然后跑两遍最短路，就能求出答案。
容易发现，这样跑出来的两遍最短路，围成的圈一定包括整个树林，然后这题就做完了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2010
#define M N*N
using namespace std;
int n,m,i,j,k,map[N][N],data[M][3],ans,sx,sy,x,y,xx,yy,bz[N][N],dis[N][N],bzk[N][N],fx[10][3];
int xpl,ypl,xpr,ypr,sum,ii,jj,yp;
char ch[N];
int main(){
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
scanf("%d%d
",&n,&m);
fx[1][1]=1;fx[1][2]=0;
fx[2][1]=-1;fx[2][2]=0;
fx[3][1]=0;fx[3][2]=1;
fx[4][1]=0;fx[4][2]=-1;
fx[5][1]=1;fx[5][2]=1;
fx[6][1]=1;fx[6][2]=-1;
fx[7][1]=-1;fx[7][2]=1;
fx[8][1]=-1;fx[8][2]=-1;
yp=1e9;
xpl=1e9;
for (i=1;i<=n;i++){
scanf("%s
",ch+1);
for (j=1;j<=m;j++){
if (ch[j]=='.') map[i][j]=1;
if (ch[j]=='X'){
map[i][j]=2;
if (i>xpr){
xpr=i;
ypr=j;
}
if (i<xpl){
xpl=i;
ypl=j;
}
yp=min(yp,j);
}
if (ch[j]=='*'){
map[i][j]=3;
sx=i;
sy=j;
}
}
}
ans=1e9;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (map[i][j]==2){
if (xpl==xpr&&sx==xpl){
ii=0;jj=1;
data[1][1]=sx;
data[1][2]=sy;
memset(bz,0,sizeof(bz));
bz[sx][sy]=1;
memset(dis,127,sizeof(dis));
dis[sx][sy]=0;
while (ii<jj){
ii++;
x=data[ii][1];y=data[ii][2];
for (k=1;k<=8;k++){
xx=x+fx[k][1];yy=y+fx[k][2];
if (xx<=n&&yy<=m&&xx>0&&yy>0&&map[xx][yy]!=2&&dis[xx][yy]>dis[x][y]+1){
dis[xx][yy]=dis[x][y]+1;
if (bz[xx][yy]==0){
bz[xx][yy]=1;
jj++;
data[jj][1]=xx;
data[jj][2]=yy;
}
}
}
}
ans=dis[xpl][yp-1]*2;
printf("%d
",ans);
return 0;
}
if (sx<xpr){
ii=0;jj=1;
data[1][1]=sx;
data[1][2]=sy;
memset(bz,0,sizeof(bz));
bz[sx][sy]=1;
memset(dis,127,sizeof(dis));
dis[sx][sy]=0;
while (ii<jj){
ii++;
x=data[ii][1];y=data[ii][2];
for (k=1;k<=8;k++){
xx=x+fx[k][1];yy=y+fx[k][2];
if (xx<=n&&yy<=m&&xx>0&&yy>0&&(yy<=ypr||xx<max(xpl,sx+1))&&map[xx][yy]!=2&&dis[xx][yy]>dis[x][y]+1){
dis[xx][yy]=dis[x][y]+1;
if (bz[xx][yy]==0){
bz[xx][yy]=1;
jj++;
data[jj][1]=xx;
data[jj][2]=yy;
}
}
}
}
ans=dis[xpr+1][ypr];
ii=0;jj=1;
data[1][1]=sx;
data[1][2]=sy;
memset(bz,0,sizeof(bz));
bz[sx][sy]=1;
memset(dis,127,sizeof(dis));
dis[sx][sy]=0;
while (ii<jj){
ii++;
x=data[ii][1];y=data[ii][2];
for (k=1;k<=8;k++){
xx=x+fx[k][1];yy=y+fx[k][2];
if (xx<=n&&yy<=m&&xx>0&&yy>0&&(yy>=ypr||xx<max(xpl,sx+1))&&map[xx][yy]!=2&&dis[xx][yy]>dis[x][y]+1){
dis[xx][yy]=dis[x][y]+1;
if (bz[xx][yy]==0){
bz[xx][yy]=1;
jj++;
data[jj][1]=xx;
data[jj][2]=yy;
}
}
}
}
ans+=dis[xpr+1][ypr];
printf("%d
",ans);
return 0;
}
ii=0;jj=1;
data[1][1]=sx;
data[1][2]=sy;
memset(bz,0,sizeof(bz));
bz[sx][sy]=1;
memset(dis,127,sizeof(dis));
dis[sx][sy]=0;
while (ii<jj){
ii++;
x=data[ii][1];y=data[ii][2];
for (k=1;k<=8;k++){
xx=x+fx[k][1];yy=y+fx[k][2];
if (xx<=n&&yy<=m&&xx>0&&yy>0&&(yy<=ypl||xx>min(xpr,sx-1))&&map[xx][yy]!=2&&dis[xx][yy]>dis[x][y]+1){
dis[xx][yy]=dis[x][y]+1;
if (bz[xx][yy]==0){
bz[xx][yy]=1;
jj++;
data[jj][1]=xx;
data[jj][2]=yy;
}
}
}
}
ans=dis[xpl-1][ypl];
ii=0;jj=1;
data[1][1]=sx;
data[1][2]=sy;
memset(bz,0,sizeof(bz));
bz[sx][sy]=1;
memset(dis,127,sizeof(dis));
dis[sx][sy]=0;
while (ii<jj){
ii++;
x=data[ii][1];y=data[ii][2];
for (k=1;k<=8;k++){
xx=x+fx[k][1];yy=y+fx[k][2];
if (xx<=n&&yy<=m&&xx>0&&yy>0&&(yy>=ypl||xx>min(xpr,sx-1))&&map[xx][yy]!=2&&dis[xx][yy]>dis[x][y]+1){
dis[xx][yy]=dis[x][y]+1;
if (bz[xx][yy]==0){
bz[xx][yy]=1;
jj++;
data[jj][1]=xx;
data[jj][2]=yy;
}
}
}
}
ans+=dis[xpl-1][ypl];
printf("%d
",ans);
return 0;
}
printf("%d
",ans);
return 0;
}