P10491 [USACO09NOV] The Chivalrous Cow B 题解
2023gdgz01
·
·
题解
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}; //纵坐标的变化方式
代码如下：
```cpp
#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 链接](https://www.luogu.com.cn/record/159234017)