题解 P2864 【[USACO06JAN]The Grove S】

· · 题解

跟类似的建墙法，不过我用的是C++，顺便再补充一点东西（

首先，我们可以在第一棵树的下方建墙，如果树用1表示，墙用2表示，空地用0表示，然后我们开一个s数组用来判重（墙和树都在s里面），再建立一个数组mp存储步数。那么s数组就是这样：

0 0 0 0 0 0 0

0 0 0 1 0 0 0

0 0 1 1 1 0 0

0 0 0 1 1 1 0

0 0 0 1 0 0 0

0 0 0 2 0 0 0

关键在于怎么判断从另一侧走向墙。由于这种墙是垂直的，所以我们可以判断y值与墙的y值的大小（一开始写的x，调了老半天了）如果从左向右走到了墙就把2改为3，如果从右向左走到了就把2改为4，最后判断走到的3或4是否相等并且是不同方向的即可。

具体见代码：

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=100;
int s[N][N];
int mp[N][N];
int dx[10]={0,-1,-1,-1,0,0,1,1,1};
int dy[10]={0,-1,0,1,-1,1,-1,0,1};
struct ss{
    int x,y,st;
};
int sx,sy;
queue <ss> q;
void bfs(){
    int ans=10010;
    while(!q.empty()){//bfs基本操作
        ss t=q.front();
        q.pop();
        if(s[t.x][t.y]>=2) continue;//判断是不是墙
        ss f;
        f.st=t.st+1;
        for(int i=1;i<=8;i++){
            f.x=t.x+dx[i],f.y=t.y+dy[i];
            if(f.x>0&&f.y>0&&f.x<=n&&f.y<=m){
                if(mp[f.x][f.y]==0){
                    if(s[f.x][f.y]==1) continue;
                    if(s[f.x][f.y]<2)s[f.x][f.y]=1;
                    else {
                        if(t.y<f.y) s[f.x][f.y]=3;
                        else s[f.x][f.y]=4;
                        //标记从哪里走向墙
                    }
                    mp[f.x][f.y]=f.st;
                    q.push(f);
                }
                else if(mp[f.x][f.y]!=0){
                    if((s[f.x][f.y]==4&&t.y<f.y)||(s[f.x][f.y]==3&&t.y>f.y)){
                    //判断是否是墙以及满足的条件
                        ans=min((mp[t.x][t.y]+mp[f.x][f.y]),ans);
                        //ans取最小值
                    }
                }
            }
        }
    }
    cout<<ans+1<<endl;//最后别忘记+1
}
int main (){
    cin>>n>>m;
    bool f=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            char ch;
            cin>>ch;
            if(ch=='X') {
                s[i][j]=1;
                if(f==0){
                    f=1;
                    for(int x=i+1;x<=n;x++) s[x][j]=2;//建墙
                }
            }
            if(ch=='*'){sx=i;sy=j;}
        }
    q.push((ss){sx,sy,0});
    bfs();
    return 0;
}

管理员大大求过