自动搬运

查看原文

来自洛谷，原作者为

	XingnoYi Connecting...... [ TIME_OUT ]

搬运于2025-08-24 22:56:00，当前版本为作者最后更新于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

1. 最开始我们在 $(2,2)$。
2. 此时，$\text{ways}[i][j] = \text{D}$，我们可以将其压入栈中。
3. D 方向的反方向为 U，于是我们向上走，回到 $(1,2)$。
4. 重复 $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$ 种写法：

1. 用 $2$ 个数组存 $\Delta x$ 和 $\Delta y$。
2. 用 $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;
}