Problem.png

騎士的移動
經(jīng)典的BFS，但是統(tǒng)計從起點到終點需要多少步的話要思考一下，每次擴(kuò)展到新方塊的時候，新方塊到起點的步數(shù)是在當(dāng)前出隊的方塊到起點的距離+1，這是一個類似于迭代的過程？？體會一下吧。。

#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
using namespace std;

struct point {
    int x;
    int y;
    
    point(int x, int y) : x(x), y(y) {}
};

// 用step數(shù)組記錄棋盤上每個方塊從起點開始走出的步數(shù)
int step[8][8];

// 騎士有八個方向可以走
int dr[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
int dc[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

int bfs(point s, point d) {
    queue<point> q;
    q.push(s);
    step[s.x][s.y] = 0;
    while (!q.empty()) {
        point u = q.front();
        q.pop();
        if (u.x == d.x && u.y == d.y) break;
        for (int i = 0; i < 8; i++) {
            int dx = u.x + dr[i];
            int dy = u.y + dc[i];
            if (dx >= 0 && dx <= 7 && dy >= 0 && dy <= 7 && step[dx][dy] < 0) {
                q.push(point(dx, dy));
                // 對于當(dāng)前方塊可以移動到的方塊，從起點走出的步數(shù)要在當(dāng)前方塊的基礎(chǔ)上+1
                step[dx][dy] = step[u.x][u.y] + 1;
            }
        }
    }
    return step[d.x][d.y];
}

int main() {
    string start, dest;
    while (cin >> start >> dest) {
        memset(step, -1, sizeof(step));
        int x1 = start[1] - '0' - 1;
        int y1 = start[0] - 'a';
        int x2 = dest[1] - '0' - 1;
        int y2 = dest[0] - 'a';
        
        point s(x1, y1);
        point d(x2, y2);
        int ans = bfs(s, d);
        printf("To get from %s to %s takes %d knight moves.\n", start.c_str(), dest.c_str(), ans);
    }
    return 0;
}