题解：P3610 [USACO17JAN] Cow Navigation G

· · 题解

P3610 [USACO17JAN] Cow Navigation G 题解

诶嘿嘿大模拟。

题意

一个点在 (n,1) 要去 (1,n)，中间有障碍物不能进入，也不能出界。可以移动或转向，都算 1 步。到达终点后停止移动和转向。求初始朝哪里都能到达终点的最小步数。

其实就是找一个最终路径序列，序列中包含“左转，右转，移动”这三个操作，使这个点一开始不管朝上还是朝右（因为左下角，所以只能有这两种朝向），按照这个序列走，都能到终点。求这个序列的长度。

思路

因为这个序列是定的，所以每一步走的必须相同。如果从起点跑两个 bfs 是肯定不行的。

可以考虑带着这两种方向一起跑，也就是把一个点灵魂分裂成俩，一个初始朝上，另一个初始朝右，每 bfs 一步都操作两个点。

当然，如果其中有一个点“到终点”或“撞墙”或“进草”，则不操作那一个点，另外一个点还是要操作的。

因为每个点都有下标 (x,y) 和方向 d，所以用六维数组存储每种情况（不是坐标，因为两个点的坐标和朝向都有可能不一样）走过的步数的最小值。

当然，得用一个六维标记数组存某种情况是否经历过，经历了就不再把那个情况入队，可能算类似 spfa 的东西吧。否则你会荣获 TLE 和 MLE。（其实什么都可能荣获）

因为最终两个点到终点后的朝向是不确定的，所以最终把每个点的 4 种朝向都遍历一遍，取 \min 就好了。

虽然很详细了，但是代码更详细。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=25,inf=0x3f3f3f3f3f3f3f3f;
int n,a[N][N],ans=inf; // ans要取最小值所以最大化
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
// 0上 1右 2下 3左，这样处理利于转向，在处理转向的时候会详细描述
int dis[N][N][5][N][N][5];
bool vis[N][N][5][N][N][5];
// x1 y1 d1 x2 y2 d2，分别是两头牛的坐标和朝向
struct ppp
{
    int x1,y1,d1,x2,y2,d2;
};
queue<ppp> q; // bfs的队列

bool inArea(int x,int y) {return x>0 && x<=n && y>0 && y<=n;}
// 判断是否撞到墙

// 这个update是当你要去一个新的坐标or换方向，去更新dis的
void update(int x1,int y1,int d1,int x2,int y2,int d2,int now)
{
    // now是原来的点的dis，走到新点的步数就是now+1
    // 当新的点比now+1还要大，说明可以更新新点的步数（因为要求最小步数）
    if(dis[x1][y1][d1][x2][y2][d2]>now+1)
    {
        dis[x1][y1][d1][x2][y2][d2]=now+1;
        // 更新
        if(!vis[x1][y1][d1][x2][y2][d2])
        {
            // 这里是类似spfa的方法，每个点只能入队一次，加快时间复杂度
            vis[x1][y1][d1][x2][y2][d2]=1;
            q.push({x1,y1,d1,x2,y2,d2});
            // 入队
        }
    }
}

void bfs()
{
    q.push({n,1,0,n,1,1});
    // {n,1}是起点，第一个牛朝上，第二个朝右，初始方向只可能是这两个
    memset(dis,0x3f,sizeof dis);
    // 求最小值记得最大化
    dis[n][1][0][n][1][1]=0;
    // 起点0步就能到
    while(!q.empty())
    {
        int x1=q.front().x1;
        int y1=q.front().y1;
        int d1=q.front().d1;
        int x2=q.front().x2;
        int y2=q.front().y2;
        int d2=q.front().d2;
        q.pop(); // 经典bfs

        // part1 : move
        int nx1=x1+dir[d1][0];
        int ny1=y1+dir[d1][1];
        int nx2=x2+dir[d2][0];
        int ny2=y2+dir[d2][1];
        // 这四个东西是如果移动的话，会移动到的坐标，因为牛朝向是定的，所以不用枚举四个方向
        int cnt=dis[x1][y1][d1][x2][y2][d2];
        // 当前点的步数
        if(!inArea(nx1,ny1) || a[nx1][ny1])
          nx1=x1,ny1=y1;
        if(!inArea(nx2,ny2) || a[nx2][ny2])
          nx2=x2,ny2=y2;
        // 这两个是如果撞墙或进草的处理，也就是不动，坐标还是之前的{x1,x2}。记得要分别处理两头牛
        if(x1==1 && y1==n)
          nx1=1,ny1=n;
        if(x2==1 && y2==n)
          nx2=1,ny2=n;
        // 这两个是如果到终点的处理，题里说了到终点后不动，坐标不变。记得要分别处理两头牛
        update(nx1,ny1,d1,nx2,ny2,d2,cnt);
        // 更新新点的步数dis，且入队

        int nd1,nd2;

        // part2 : left turn
        nd1=d1-1,nd2=d2-1;
        // 因为定的是0上1右2下3左，所以左转+1，右转-1，非常方便
        if(nd1<0)
          nd1=3;
        if(nd2<0)
          nd2=3;
        // 0上，左转变成-1，但其实是3左。记得要分别处理两头牛
        update(x1,y1,nd1,x2,y2,nd2,cnt);
        // 更新新点的步数dis，且入队

        // part3 : right turn
        nd1=d1+1,nd2=d2+1;
        // 这里同上
        if(nd1==4)
          nd1=0;
        if(nd2==4)
          nd2=0;
        // 3左，右转变成4，但其实是0上。记得要分别处理两头牛
        update(x1,y1,nd1,x2,y2,nd2,cnt);
        // 更新新点的步数dis，且入队
    }
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        for(int j=1;j<=n;j++)
          a[i][j]=(s[j-1]=='H'); // 如果是H则有草，标记为1，不能进入
    }
    bfs();
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
          ans=min(ans,dis[1][n][i][1][n][j]);
          // 终点{1,n}，每头牛的4种方向的最终步数都要计算，取min
    return !printf("%lld\n",ans);
}

给我赞赞 qwq