P10234 找机厅

XingnoYi · 2024-03-10 10:56:03 · 题解

超详细的题解！

前言：~~当一个音游人看到这场比赛，他的内心……~~

这题调了足足 3 个小时，全是细节错误。

要不是 VS Code，我估计这辈子都调不出来。

如下 big 代表 long long。

思路分析：

子问题 1：

问题简述：找出起点到终点的最短路径长度。

这应该很好想，就是一道 BFS 的模板题，和 P1141 01迷宫比较相似。

如果你不会 BFS，可以看一下概述。

子问题 2：

问题概述：输出该最短路径的行走方式。

在纯 BFS 中应该无法直接回溯找到路径的。

1. \text{ways} 数组：

我们可以加入数组 \text{ways}[i][j]，该数组表示这个格子是由上一个格子从什么方向到达的，以方便路径逆推。

用样例举例：

01
10

该图的一种 \text{ways} 数组表示如下：

0 R 
D D

你会发现，这幅图最短路径的的走法就是 (1,1)\to (1,2) \to (2,2)，即 RD。

你也许会问：这只是起点到终点的走法，那 BFS 最后已经到终点了，怎么用这个数组来找路径呢？

2. 逆推求路径：

想一想，你走到终点了，那只需要从终点开始，记录每个点的 \text{ways} 值，再往反方向走，直到走回起点为止。

这样，只需要将记录的 \text{ways} 值反向输出即可。

如何反向输出？

可以用栈或字符串。

我使用的是栈的方法。

同样地，以该图举例：

0 R 
D D

最开始我们在 (2,2)。
此时，\text{ways}[i][j] = \text{D}，我们可以将其压入栈中。
D 方向的反方向为 U，于是我们向上走，回到 (1,2)。
重复 2 和 3 操作直到回到 (1,1)。

BFS 函数的代码：

void bfs(big sx,big sy) // bfs 模板
{
    queue <Node> q;
    q.push(Node({sx,sy}));
    dis[sx][sy] = 0;
    vis[sx][sy] = 1;
    while(!q.empty())
    {
        Node pos=q.front();
        q.pop();
        if(pos.x == n && pos.y == m)
        {
            printf("%lld\n",dis[n][m]);
            // 因为需要逆序输出，这里用一个栈存储路径。
            // 用字符串反向输出也可以。
            stack <big> st;
            big ex = n,ey = m;
            while((ex != 1) || (ey != 1))
            {
                st.push(ways[ex][ey]); // 正向存储
                big back = (ways[ex][ey]+2)%4; // 反向回溯
                ex += to[back][0], ey += to[back][1]; // 回溯
            }
            while(!st.empty())
            {
                putchar(path[st.top()]); // 反向输出路径
                st.pop();
            }
            putchar('\n');
            return;
        }
        big ax = pos.x, ay = pos.y;
        for(big i = 0;i < 4;i++)
        {
            big nowx = ax+to[i][0], nowy = ay+to[i][1]; 
            if((vis[nowx][nowy] == 0) && (mapp[nowx][nowy] != mapp[ax][ay]) && (1 <= ax && ax <= n && ay >= 1 && ay <= m)) 
            {
                ways[nowx][nowy] = i;
                dis[nowx][nowy] = dis[ax][ay]+1;
                vis[nowx][nowy] = 1;
                q.push(Node({nowx,nowy}));
            }
        }
    }
    // 若没有到终点就无法继续了，说明无解。
    printf("-1\n");
}

坑点简述：

~~气死我了……~~

坑点 1：

关于方向数组，一般有 2 种写法：

用 2 个数组存 \Delta x 和 \Delta y。
用 1 个二维数组同时存一个数对 (\Delta x,\Delta y)。

当使用第 2 种方向时，一定要注意数组两个维度的定义。

对比如下代码：

to[4][2]={1,0,0,1,-1,0,0,-1};
big nowx = ax+to[i][0], nowy = ay+to[i][1];

to[2][4]={1,0,0,1,-1,0,0,-1};
big nowx = ax+to[0][i], nowy = ay+to[1][i];

乍一看是不是没什么区别？

其实第一种是对的。

看一下 VS Code 中对两种数组的概况描述。

to[4][2] 这种定义是一个 4 行 2 列的数组，每行存一个数对 (\Delta x,\Delta y)，表示增减值。

而 to[2][4] 这种定义是一个 2 行 4 列的数组，每行存一个数组，分别表示 \Delta x 和 \Delta y。

很显然，第二种方案的 (\Delta x,\Delta y) 就变成了：

(1,-1)
(0,0)
(0,0)
(1,-1)

是错误的。

一般来说，我们都会输入 4 个数对，而不是分两行输入，所以我推荐用 \text{to}[4][2] 来存储。

坑点 2：

多测清空时不要用 memset()，也不要直接全部清空。

应该先确定大小再清空。

坑点 3：

在循环判断是否回到起点时，所用的判断条件为：

while((ex != 1) || (ey != 1)) // 坑点3：用或而不是且。

不过要很好地避免此类问题，可以用：

while(!((ex == 1) && (ey == 1)))

完整代码：

#include <iostream>
#include <queue>
#include <stack>
#define big long long
using namespace std;
struct Node{
    big x,y;
};
big T,n,m,to[4][2]={1,0,0,1,-1,0,0,-1}; // 坑点1：方向数组应用。二维数组应用 [4][2] 而不是 [2][4]。
char path[5]={'D','R','U','L'}; // 方向要对应，为简化代码，采用逆时针存储方向。
big ways[3004][3004],dis[3004][3004];
// ways[i][j] 表示这个格子是由上一个格子从什么方向到达的（以方便路径逆推）。
// dis[i][j] 表示该点到起点的距离。
bool vis[3004][3004],mapp[3004][3004]; // 是否到达过；存地图
void bfs(big sx,big sy) // bfs 模板
{
    queue <Node> q;
    q.push(Node({sx,sy}));
    dis[sx][sy] = 0;
    vis[sx][sy] = 1;
    while(!q.empty())
    {
        Node pos=q.front();
        q.pop();
        if(pos.x == n && pos.y == m)
        {
            printf("%lld\n",dis[n][m]);
            // 因为需要逆序输出，这里用一个栈存储路径。
            // 用字符串反向输出也可以。
            stack <big> st;
            big ex = n,ey = m;
            while((ex != 1) || (ey != 1)) // 坑点3：用或而不是且。
            {
                st.push(ways[ex][ey]); // 正向存储
                big back = (ways[ex][ey]+2)%4; // 反向回溯
                ex += to[back][0], ey += to[back][1]; // 回溯
            }
            while(!st.empty())
            {
                putchar(path[st.top()]); // 反向输出路径
                st.pop();
            }
            putchar('\n');
            return;
        }
        big ax = pos.x, ay = pos.y;
        for(big i = 0;i < 4;i++)
        {
            big nowx = ax+to[i][0], nowy = ay+to[i][1]; 
            if((vis[nowx][nowy] == 0) && (mapp[nowx][nowy] != mapp[ax][ay]) && (1 <= ax && ax <= n && ay >= 1 && ay <= m)) 
            {
                ways[nowx][nowy] = i;
                dis[nowx][nowy] = dis[ax][ay]+1;
                vis[nowx][nowy] = 1;
                q.push(Node({nowx,nowy}));
            }
        }
    }
    // 若没有到终点就无法继续了，说明无解。
    printf("-1\n");
}
int main()
{
    scanf("%lld\n",&T);
    while(T--)
    {
        scanf("%lld %lld\n",&n,&m);
        // 坑点2：先输入再清空，降低复杂度。
        for(big i = 0;i <= n;i++)
        {
            for(big j = 0;j <= m;j++)
            {
                vis[i][j] = 0;
                dis[i][j] = ways[i][j] = 0;
            }
        }
        for(big i = 1;i <= n;i++)
        {
            for(big j = 1;j <= m;j++)
            {
                // 注意读入 '\n' 导致答案错误
                char ch = getchar();
                while(ch != '0' && ch != '1')
                {
                    ch = getchar();
                }
                mapp[i][j] = ch-'0';
            }
        }
        if((mapp[n-1][m] == mapp[n][m]) && (mapp[n][m-1] == mapp[n][m])) // 小小优化
        {
            printf("-1\n");
            continue;
        }
        bfs(1,1);
    }
    return 0;
}