题解 P4818 【[USACO15DEC]Bessie's Dream 贝西的梦】

· · 题解

大搜索。因为允许多次在可行的情况下走过一个点，所以在这里我们记录状态，若当前状态未出现过则继续搜索。

本题使用STL queue，因为枚举次数不宜确定，数组大小不确定。手写导致我wa了许多次。队列结构体维护坐标，方向，橙子味，距离。

当a[x][y]==4时，不同的方向会造成不同的结果，所以要记录方向。剩下就不再赘述了。

搜索过程中不用使用判重数组的原因是边界外的点的值是0，与红色格子的值相同。

代码：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <queue>
static const int MAXN=1050;
static const int dirx[]={1,-1,0,0};
static const int diry[]={0,0,1,-1};
using namespace std;
struct node{
    int x,y,d,ora,dis;
};
queue<node> q;
int n,m,head,tail,a[MAXN][MAXN];
bool vis[MAXN][MAXN][2][5];
inline int read(){
    int x=0;bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline bool check(int x,int y){
    return (x<1||y<1||x>n||y>m)?true:false;
}
inline int bfs(){
    q.push((node){1,1,0,0,0});
    while(!q.empty()){
        node now=q.front();q.pop();
        int x=now.x,y=now.y,d=now.d,ora=now.ora,dis=now.dis;
        bool flag=0;
        if(vis[x][y][ora][d]) continue;
        vis[x][y][ora][d]=1;
        if(x==n&&y==m) return dis;
        if(a[x][y]==4){
            int dx=x+dirx[d],dy=y+diry[d];
            if(!a[dx][dy]||a[dx][dy]==3);
            else if(a[dx][dy]==1||a[dx][dy]==4) q.push((node){dx,dy,d,0,dis+1}),flag=1;
            else q.push((node){dx,dy,d,1,dis+1}),flag=1;
        }
        if(a[x][y]==4&&flag) continue;
        for(int i=0;i<4;i++){
            int dx=x+dirx[i],dy=y+diry[i];
            if(!a[dx][dy]||(a[dx][dy]==3&&!ora)) continue;
            else if((a[dx][dy]==3&&ora)||a[dx][dy]==1||a[dx][dy]==4) q.push((node){dx,dy,i,ora,dis+1});
            else if(a[dx][dy]==2) q.push((node){dx,dy,i,1,dis+1});
        }
    }
    return -1;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
        }
    }
    printf("%d\n",bfs());
    return 0;
}