题目描述
农民 John 有很多牛,他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力,在农场里像 Knight 一样地跳(就是我们熟悉的象棋中马的走法)。
虽然这头神奇的牛不能跳到树上和石头上,但是它可以在牧场上随意跳,我们把牧场用一个 $x,y$ 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草,给你一张地图,上面标注了 The Knight 的开始位置,树、灌木、石头以及其它障碍的位置,除此之外还有一捆草。
现在你的任务是,确定 The Knight 要想吃到草,至少需要跳多少次。
The Knight 的位置用 K
来标记,障碍的位置用 *
来标记,草的位置用 H
来标记。
这里有一个地图的例子:
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . H
5 | * . . . . . . . . .
4 | . . . * . . . * . .
3 | . K . . . . . . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0
The Knight 可以按照下图中的 $A,B,C,D…$ 这条路径用 $5$ 次跳到草的地方(有可能其它路线的长度也是 $5$):
11 | . . . . . . . . . .
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . F<
5 | * . B . . . . . . .
4 | . . . * C . . * E .
3 | .>A . . . . D . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
1
0 1 2 3 4 5 6 7 8 9 0
注意: 数据保证一定有解。
输入格式
第 $1$ 行: 两个数,表示农场的列数 $C$ 和行数 $R$。
第 $2..R+1$ 行: 每行一个由 $C$ 个字符组成的字符串,共同描绘出牧场地图。
输出格式
一个整数,表示跳跃的最小次数。
数据范围
$1≤R,C≤150$
输入样例:
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..
输出样例:
5
题目分析
看到题目里面的 “最小次数” 这个词,你应该首先想到的就是 bfs (当然直接看算法标签也行)
bfs 要考虑的四点是:
- 状态描述
- 起始状态
- 终止状态
- 状态间的转移
状态描述
这道题里的状态就是一个二维坐标和起点到它走了多少步。二维坐标可以用pair<int, int>
实现,起点到它走了多少步可以用dist
数组记录。
起始状态
这道题里的起始状态就是地图上标注着K
的地方,它到自己的距离当然是0
。找到标注着K
的地方的坐标可以用两层for
循环,也可以用STL里面的find
一行一行找。
终止状态
这道题里的终止状态就是地图上标注着H
的地方,如果搜到了就返回起点到它走了多少步。
状态间的转移
这道题里的状态间的转移就是国际象棋中马的走法,如下图(马标作K
,马能到的地方标作*
,剩余地方标作.
):(注意:国际象棋没有 “蹩马腿” 一说!不要和中国象棋搞混了!)
.*.*.
*...*
..K..
*...*
.*.*.
坐标的变化量可以用dx
和dy
数组记录。
代码(带注释)
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 160; // 开大10保险一点
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; // 坐标变化量
int n, m; // 地图的长和宽
char g[N][N]; // 地图
PII q[N * N]; // bfs要用的队列(我习惯用手写队列,但是也可以用STL里面的queue)
int dist[N][N]; // dist数组记录距离
bool st[N][N]; // st数组记录是否被搜过(也可以像y总那样不用st,把dist全初始化成-1,然后判断dist[x][y]是不是-1)
int bfs()
{
int hh = 0, tt = 0; // 队头和队尾(队尾是0是因为要添加起点)
int a, b; // 'K'所在的坐标
for (int i = 0; i < n; i ++ ) // 搜!
for (int j = 0; j < m; j ++ ) // 注意是m
if (g[i][j] == 'K')
a = i, b = j;
q[0] = {a, b}; // 起点坐标入队
dist[a][b] = 0; // 起点到自己的距离是0
st[a][b] = true; // 标记一下起点搜过了
while (hh <= tt) // 当队列不为空
{
PII t = q[hh ++ ]; // 弹出队头
if (g[t.x][t.y] == 'H') return dist[t.x][t.y]; // 如果搜到终点了则返回
for (int i = 0; i < 8; i ++ ) // 遍历所有的方向
{
int a = t.x + dx[i], b = t.y + dy[i]; // 计算坐标
if (a < 0 || a >= n || b < 0 || b >= m) continue; // 如果跳出来地图则跳过
if (st[a][b]) continue; // 如果搜过了也跳过
if (g[a][b] == '*') continue; // 不能跳到障碍上
q[ ++ tt] = {a, b}; // 入队
dist[a][b] = dist[t.x][t.y] + 1; // 起点到新的点的距离是起点到原来的点t的距离 + 1
st[a][b] = true; // 这个点也被搜过了
}
}
return -1; // 因为数据保证有解所以不会被执行到,但是加上了会方便调试
}
int main()
{
cin >> m >> n; // 这里有个坑点:是先输入列数再输入行数
for (int i = 0; i < n; i ++ ) cin >> g[i]; // 读取地图的每一行
cout << bfs(); // 输出结果
return 0;
}
代码(不带注释)我知道你们最喜欢这个
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 160;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;
char g[N][N];
PII q[N * N];
int dist[N][N];
bool st[N][N];
int bfs()
{
int hh = 0, tt = 0;
int a, b;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'K')
a = i, b = j;
q[0] = {a, b};
dist[a][b] = 0;
st[a][b] = true;
while (hh <= tt)
{
PII t = q[hh ++ ];
if (g[t.x][t.y] == 'H') return dist[t.x][t.y];
for (int i = 0; i < 8; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (st[a][b]) continue;
if (g[a][b] == '*') continue;
q[ ++ tt] = {a, b};
dist[a][b] = dist[t.x][t.y] + 1;
st[a][b] = true;
}
}
return -1;
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> g[i];
cout << bfs();
return 0;
}
代码(STL版)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 160;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;
char g[N][N];
queue<PII> q;
int dist[N][N];
bool st[N][N];
int bfs()
{
int a, b;
for (int i = 0; i < n; i ++ )
{
int j = find(g[i], g[i] + m, 'K') - g[i];
if (j != m)
{
a = i, b = j;
break;
}
}
q.push({a, b});
dist[a][b] = 0;
st[a][b] = true;
while (!q.empty())
{
PII t = q.front(); q.pop();
if (g[t.x][t.y] == 'H') return dist[t.x][t.y];
for (int i = 0; i < 8; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (st[a][b]) continue;
if (g[a][b] == '*') continue;
q.push({a, b});
dist[a][b] = dist[t.x][t.y] + 1;
st[a][b] = true;
}
}
return -1;
}
int main()
{
cin >> m >> n;
for (int i = 0; i < n; i ++ ) cin >> g[i];
cout << bfs();
return 0;
}