自动搬运

查看原文

来自洛谷，原作者为

	2023gdgz01 义忠仁

搬运于2025-08-24 22:58:31，当前版本为作者最后更新于2024-05-17 15:00:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

bfs 模板题。

用队列 $q$ 来存储遍历的点，其类型为 queue<pair<int, int> >；用 $dis_{(x,y)}$ 记录从起点到 $(x,y)$ 的距离。初始时，$q$ 中仅有起点 $(sx,sy)$，即 The Knight 的初始位置，$dis_{(i,j)}=\begin{cases}0&i=sx,j=sy\\-1&\operatorname{otherwise}\end{cases}$，其中 $-1$ 表示未到达。

当 $q$ 不为空时，取出队首并存入 $temp$。若已到达草的位置，则结束 bfs；否则更新 $temp$ 能够到达的点。象棋中马的走法如下（a 表示当前位置，b 表示可能到达的位置，. 表示其它位置）：

.b.b.
b...b
..a..
b...b
.b.b.

由此，我们可以求出偏移量数组，即下一步坐标的变化方式：

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; //横坐标的变化方式
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; //纵坐标的变化方式

$temp$ 下一步的更新就依赖于偏移量数组，具体如下：遍历偏移量数组，求出可能的下一步 $(nx,ny)$，其中 nx = temp.first + dx[i], ny = temp.second + dy[i]，若 $(nx,ny)$ 不越界、未访问且不是灌木，则称 $(nx,ny)$ 位置合法，并将 $(nx,ny)$ 入队，dis[nx][ny] = dis[temp.first][temp.second] + 1;，完成更新。可结合代码理解。

代码如下：

#include <iostream>
#include <cstring>
#include <utility>
#include <queue>

using namespace std;

char g[155][155];
int n, m, sx, sy, ex, ey, nx, ny, dis[155][155], dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
queue<pair<int, int> > q;
pair<int, int> temp;

inline int bfs() { //广度优先搜索
	q.push(make_pair(sx, sy));
	memset(dis, -1, sizeof(dis));
	dis[sx][sy] = 0;
	while (!q.empty()) {
		temp = q.front(); //队首出队
		q.pop();
		if (temp.first == ex && temp.second == ey) //到达草的位置
			return dis[ex][ey];
		for (register int i = 0; i < 8; ++i) { //更新下一步
			nx = temp.first + dx[i];
			ny = temp.second + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > m || dis[nx][ny] != -1 || g[nx][ny] == '*') //下一步位置不合法
				continue;
			q.push(make_pair(nx, ny)); //合法位置入队
			dis[nx][ny] = dis[temp.first][temp.second] + 1; //更新距离
		}
	}
	//如果执行到这就说明到达不了草的位置，数据出错了
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> m >> n; //坑人
	for (register int i = 1; i <= n; ++i)
		for (register int j = 1; j <= m; ++j) {
			cin >> g[i][j];
			if (g[i][j] == 'K') { //确定 Knight 的位置
				sx = i;
				sy = j;
			}
			if (g[i][j] == 'H') { //确定草的位置
				ex = i;
				ey = j;
			}
		}
	cout << bfs();
	return 0;
}

时间复杂度为 $O(nm)$。AC 链接