题解 P2864 【[USACO06JAN]The Grove S】

Joker_M · 2020-12-03 07:31:49 · 题解

蒟蒻打模拟赛时遇到的原题...（太菜了直接被吊着打）
题意：给定一张图，图中有不可经过的点（标记为 X ），求从起点出发绕所有的 X 一圈所需的最小步数。（保证所有 X 位于一个联通块）
由于是类似走迷宫求最小步数的题，很容易想到用 bfs 求最短路，但是存在一个问题：bfs 只能求出起点到所有点的最短路，如果按照题目绕一圈 X ，则必然有部分点要绕远路到达，这违背了 bfs 求出的最短路。
举个栗子：

以图中标蓝色的点为例，红色的路径是我们 bfs 求出的最短路，但为了满足题目中绕一圈 X 的要求，我们不得不绕远路到达该点（即绿色的路径）。
但计算机又不是人，怎么让他知道哪些点该绕远路，哪些点不该绕呢？
仔细观察，我们发现，如果要让那个标蓝色的点绕远路到达，则他不能从下面经过 X ，必须从上面绕过 X 到达该点，于是做法便呼之欲出了：
从最后一个 X 开始，向下建一堵无法通过的墙，如图（黑色部分即为墙）：

由于墙无法通过，到达蓝点的位置便改成的绿色的路径，正好符合了要求，现在只剩下一个问题：如何统计答案？
显然，我们只需要把墙拆掉，选择墙两边的点连结起来即可。
可以简单地证明，只需拆掉位于最上面的一堵墙即可得到最优解，设墙的位置为 (x,y) ,则答案为:

Tip:

1. 由于可以斜着走，转移时从左边有3个点可选，右边有3个点可选，取最小值即可
2. 从左边走到墙，再从墙走到右边，需要再花费两步，故 ans 要加 2

最后贴代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

char s[55][55];
int n,m;
int lx,ly;//lx，ly表示所建的第一堵墙的位置 
int sx,sy;//sx，sy表示起点位置 
int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};//位移数组 
int dis[55][55];

struct stk{
    int x,y,z;
};

inline long long read(){
    long long re=0,k=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') k=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        re=re*10+ch-'0';
        ch=getchar();
    }
    return re*k;
}

inline void bfs(){//bfs求最短路 
    queue<stk> q;
    memset(dis,0x3f,sizeof(dis));
    q.push((stk){sx,sy,0});
    dis[sx][sy]=0;
    while(!q.empty()){
        int a=q.front().x,b=q.front().y,c=q.front().z;
        q.pop();
        for(register int i=0;i<8;i++){
            int tx=a+dx[i],ty=b+dy[i];
            if(dis[tx][ty]!=0x3f3f3f3f) continue;
            if(s[tx][ty]=='X'||s[tx][ty]=='|')  continue;//墙和树林都不能走 
            if(tx<0||tx>n||ty<0||ty>m)  continue; //不可越界 
            dis[tx][ty]=c+1; 
            q.push((stk){tx,ty,c+1});
        }
    }
    return ;
}

int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=m;j++){
            cin>>s[i][j];
            if(s[i][j]=='*')    sx=i,sy=j;
            if(s[i][j]=='X')    lx=i,ly=j;//记录最后一个树林的位置 
        }
    }
    lx++;
    for(register int i=lx;i<=n;i++) s[i][ly]='|';//建墙 
    bfs();
    int ans1=min(dis[lx-1][ly-1],min(dis[lx][ly-1],dis[lx+1][ly-1]));//统计答案 
    int ans2=min(dis[lx-1][ly+1],min(dis[lx][ly+1],dis[lx+1][ly+1]));
    printf("%d\n",ans1+ans2+2); 
    return 0;
}