题解 P2864 【[USACO06JAN]The Grove S】

zmza · 2020-10-20 23:01:08 · 题解

这个是建墙法。就是建一座墙，然后bfs。就变成了从出发点到墙，再从墙到出发点的问题。

代码：

#include<bits/stdc++.h>
using namespace std;
const int dx[8]={-1,1,0,0,-1,-1,1,1};
const int dy[8]={0,0,-1,1,-1,1,-1,1};
struct node
{
    int x,y,k;
    node(int a,int b,int c):x(a),y(b),k(c)
    {
    }
    node(){
    }
    friend bool operator <(node a,node b)
    {
        return a.k > b.k;
    }
};
priority_queue<node>q;
char mp[55][55];
bool vis[55][55];
int r,c;
int gx,gy,tx,ty,d[55][55][2];
bool across(node a,node b)//判断是否穿过墙
{
    if(gx == a.x && gy > a.y && gx > b.x)
    {
        return 1;
    }
    if(gx == b.x && gy > b.y && gx > a.x)
    {
        return 1;
    }
    return 0;
}
void bfs()//广搜
{
    while(q.size())
    {
        node bei = q.top(),yong;
        q.pop();
        int x = bei.x;
        int y = bei.y;
        int k = bei.k;
        for(int i = 0; i < 8; i++)
        {
            int xx = dx[i] + x;
            int yy = dy[i] + y;
            yong = node(xx,yy,k);
            if(xx < 0 || xx >= r || yy < 0 || yy >= c || vis[xx][yy] == 1)
            {
                continue;
            }
            if(across(bei,yong))
                yong.k ^= 1;
            if(d[yong.x][yong.y][yong.k] <= d[bei.x][bei.y][bei.k] + 1)
            {
                continue;
            }
            d[yong.x][yong.y][yong.k] = d[bei.x][bei.y][bei.k] + 1;
            q.push(yong);
        }
    }
}
int main()
{
    freopen("grove.in","r",stdin);
    freopen("grove.out","w",stdout);
    scanf("%d%d",&r,&c);
    memset(d,0x7f,sizeof(d));
    for(int i = 0; i < r; i++)
    {
        scanf("%s",mp[i]);
        for(int j = 0; j < c; j++)
        {
            if(mp[i][j] == 'X')//建墙
            {
                vis[i][j] = 1;
                if(!gy)
                {
                    gx = i,gy = j;
                }
            }
            else if(mp[i][j] == '*')//出发点
            {
                tx = i,ty = j;
                d[i][j][0] = 0;
                q.push(node(i,j,0)); 
            }
        }
    }
    bfs();//开始广搜
    printf("%d",d[tx][ty][1]);//输出答案
    return 0;
}