python/TangDou/AcWing/MiniPath/188.md

AcWing 188. 武士风度的牛

一、题目描述

农民 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

二、坐标分析

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;

#define x first
#define y second
typedef pair<int, int> PII;
/*
不再是简单的4连通或8连通，而是按中国象棋的“日”的方式去走！
日：共8个方向
K:起点，H：终点，*：障碍， .:可以跳

就是一个BFS最短路径问题，关键在于如何跳“日”,其实本质还是dx8的参数配置问题了。
*/
const int N = 155, M = N * N;
int n, m;
char g[N][N];
PII q[M];
int dist[N][N]; // 距离数组

// 8个方向
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int ans = INF;

void bfs() {
    // 初始化距离数组为-1
    memset(dist, -1, sizeof dist);
    // 出发点坐标
    int sx, sy;
    // 找出发点
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'K') sx = i, sy = j;

    // 队列
    int hh = 0, tt = -1;
    q[++tt] = {sx, sy};
    dist[sx][sy] = 0; // 标识走过，防止走回头路

    while (hh <= tt) {
        PII t = q[hh++];
        for (int i = 0; i < 8; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] == '*') continue; // 障碍的位置用 * 来标记
            if (~dist[x][y]) continue;    // 已经走过不能再走，防止走回头路
            if (g[x][y] == 'H') {         // 草的位置用 H 来标记。
                ans = dist[t.x][t.y] + 1; // 多跳一步吃到草
                return;                   // 吃到草就OK了
            }
            dist[x][y] = dist[t.x][t.y] + 1; // 多跳一步
            q[++tt] = {x, y};                // 入队列继续扩展
        }
    }
}
int main() {
    cin >> m >> n; // 居然先输入列数，再输入行数，bt!

    // 这个输入太讨厌了，居然只是按行读入，每次读取一行，那么cin读到的就是一个字符串，目标是一个字符数组的话，就直接进入字符数组了~，这与以前的题目不同，要注意
    for (int i = 0; i < n; i++) cin >> g[i]; // 题意下标从0开始，注意~
    // 找最短路
    bfs();
    // 输出
    printf("%d\n", ans);
    return 0;
}