算法题：武士风度的牛

问题描述

农民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 ----------------------
   0 1 2 3 4 5 6 7 8 9 10 

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 ----------------------
   0 1 2 3 4 5 6 7 8 9 10

输入格式

第一行：两个数，表示农场的列数(≤150)和行数(≤150)

第二行~结尾: 如题目描述的图

输出格式

一个数，表示跳跃的最小次数。

样例

输入

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

输出

5

解决方案

思路

广度优先搜索 && 贪心

这个题直接使用广度优先搜索也通过了，也有可能只是测试数据不够大

但是如果测试数据很大的话，就需要使用贪心了，也就是大的范围内往终点靠近就好了。

代码

#include <iostream>
#include <queue>

using namespace std;


struct Obj {
    int x;
    int y;
    int ans;
};


char arr[155][155];
queue<Obj> q;
int n, m;
int hx, hy;

int bfs() {

    int offset_x[] = {1, -1, 2, -2, 1, -1, 2, -2};
    int offset_y[] = {2, -2, 1, -1, -2, 2, -1, 1};

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int ans = q.front().ans;
        q.pop();

        for (int i = 0; i < 8; ++i) {
            int xx = offset_x[i] + x;
            int yy = offset_y[i] + y;

            if (xx < 0 || xx >= m || yy < 0 || yy >= n)
                continue;


            if (arr[xx][yy] == 'H')
                return ans + 1;

            if (arr[xx][yy] != '.')
                continue;


            // 大距离中 距离更远的不考虑
            // 判断x是否属于大距离
            if (hx - x > 7 || x - hx > 7) {
                // 如果终点在x的上面 反而新的xx在x的下面
                if (x > hx && xx > x)
                    continue;
                // 如果终点在x的下面 反而新的xx在x的上面
                else if (x < hx && xx < x)
                    continue;
            }
            // 判断y是否属于大距离
            if (hy - y > 7 || y - hy > 7) {
                // 如果终点在y的左边 反而新的yy在y的右边
                if (y > hy && yy > y)
                    continue;
                // 如果终点在y的右边 反而新的yy在y的左边
                else if (y < hy && yy < y)
                    continue;
            }


            arr[xx][yy] = 'K';
            Obj obj;
            obj.x = xx;
            obj.y = yy;
            obj.ans = ans + 1;
            q.push(obj);
        }
    }

    return -1;
}

int main() {

    cin >> n >> m;

    int x, y;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            char t;
            cin >> t;
            arr[i][j] = t;
            if (t == 'K') {
                x = i;
                y = j;
            } else if (t == 'H') {
                hx = i;
                hy = j;
            }
        }
    }

    Obj obj;
    obj.x = x;
    obj.y = y;
    obj.ans = 0;
    q.push(obj);

    cout << bfs();

    return 0;
}