题解 P3610 【[USACO17JAN]Cow Navigation奶牛导航】

· · 题解

知识点：六维BFS

就一个bfs但是调了好几个小时（临界条件好麻烦

（虽然代码中有注释 但我还是想讲(tu)讲(cao)

因为有两头牛而且N值比较小 我们可以用六维数组模拟出每一个牛的朝向和位置

f[x1][y1][x2][t2][d1][d2]含义如上

还要注意临界条件：边界和障碍要判断 判断牛是否应该回到来时的点

然后就是进栈 更新什么的

这里我用了传址& 也可以直接Ctrl+C Ctrl+V来省事（不是复制My Code

接下来判断左转右转 特判一下方向：以免出负号RE

因为我们不知道最后的牛的脸朝哪儿 于是枚举方向即可求出答案

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#define MAXN 100005
#define LL long long
#define INF 2147483647
#define MOD 1000000007
#define free(s) freopen("s.txt","r",stdin);
#define lowbit(x) ((x&(-x))) 
#define debug(x) cout<<x<<endl;
using namespace std;
const int L=21;
int n,map[L][L],f[L][L][L][L][5][5],ans=INF,dx[]={0,-1,0,1,0},dy[]={0,0,1,0,-1};
bool vis[L][L][L][L][5][5];
struct node{
    int x1,x2,y1,y2,d1,d2;
    node (int x1,int y1,int x2,int y2,int d1,int d2):x1(x1),y1(y1),x2(x2),y2(y2),d1(d1),d2(d2) {}
    node () {}
};
int ex(char ch)
{
    if(ch=='E')
        return 1;
    return 0;
}
bool judge(int x,int y)
{
    return (x>=1)&&(x<=n)&&(y>=1)&&(y<=n);
}
void bfs()
{
    queue<node>q;
    q.push(node(n,1,n,1,1,2));
    while(!q.empty())
    {
        node head=q.front();
        q.pop();
        int nx1,nx2,ny1,ny2;        //直走 
        nx1=head.x1+dx[head.d1];
        ny1=head.y1+dy[head.d1];
        nx2=head.x2+dx[head.d2];
        ny2=head.y2+dy[head.d2];
        int cnt=f[head.x1][head.y1][head.x2][head.y2][head.d1][head.d2];
        if(!judge(nx1,ny1)||(!map[nx1][ny1]))//牛一不能直走 再回来 
            nx1=head.x1,ny1=head.y1;
        if(!judge(nx2,ny2)||(!map[nx2][ny2]))//牛二不能直走 再回来 
            nx2=head.x2,ny2=head.y2;
        if(head.x1==1&&head.y1==n)//牛一走到边界 不能移动 
            nx1=1,ny1=n;
        if (head.x2==1&&head.y2==n)//牛二走到边界 不能移动 
            nx2=1,ny2=n;
        int &p=f[nx1][ny1][nx2][ny2][head.d1][head.d2];
        if(p>cnt+1)//进栈 更新 
        {
            p=cnt+1;
            if(!vis[nx1][ny1][nx2][ny2][head.d1][head.d2])
            {
                vis[nx1][ny1][nx2][ny2][head.d1][head.d2]=1;
                q.push(node(nx1,ny1,nx2,ny2,head.d1,head.d2));
            }
        } 
        int d1,d2;
        d1=head.d1-1,d2=head.d2-1;      //左转 
        if(!d1) d1=4; if(!d2) d2=4;
        int &u=f[head.x1][head.y1][head.x2][head.y2][d1][d2];
        if(u>cnt+1)//进栈 更新 
        {
            u=cnt+1;
            if(!vis[head.x1][head.y1][head.x2][head.y2][d1][d2])
            {
                vis[head.x1][head.y1][head.x2][head.y2][d1][d2]=1;
                q.push(node(head.x1,head.y1,head.x2,head.y2,d1,d2));
            }
        }
        d1=head.d1+1,d2=head.d2+1;      //右转 
        if(d1==5) d1=1;if(d2==5) d2=1;
        int &r=f[head.x1][head.y1][head.x2][head.y2][d1][d2];
        if(r>cnt+1)//进栈 更新 
        {
            r=cnt+1;
            if(!vis[head.x1][head.y1][head.x2][head.y2][d1][d2])
            {
                vis[head.x1][head.y1][head.x2][head.y2][d1][d2]=1;
                q.push(node(head.x1,head.y1,head.x2,head.y2,d1,d2));
            }   
        }
    }
}
int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            char c;
            cin>>c;
            map[i][j]=ex(c);
        }
    f[n][1][n][1][1][2]=0;
    bfs();
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            ans=min(ans,f[1][n][1][n][i][j]);//枚举最后的朝向 
    printf("%d",ans);
    return 0;
}