Problem.png
騎士的移動(dòng)
經(jīng)典的BFS磷瘤，但是統(tǒng)計(jì)從起點(diǎn)到終點(diǎn)需要多少步的話要思考一下，每次擴(kuò)展到新方塊的時(shí)候，新方塊到起點(diǎn)的步數(shù)是在當(dāng)前出隊(duì)的方塊到起點(diǎn)的距離+1挎塌，這是一個(gè)類(lèi)似于迭代的過(guò)程？内边？體會(huì)一下吧榴都。。
#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ù)組記錄棋盤(pán)上每個(gè)方塊從起點(diǎn)開(kāi)始走出的步數(shù)
int step[8][8];
// 騎士有八個(gè)方向可以走
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));
// 對(duì)于當(dāng)前方塊可以移動(dòng)到的方塊漠其，從起點(diǎn)走出的步數(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;
}
