Knight Moves
依葫芦画瓢，葫芦在这里：
Dungeon Master
代码几乎一样的套路吧~再注意两点：
- 注意行列与自己设的 x y 坐标的关系！！（竖 x 横 y）
- 注意每一次循环将队列清空：
while(!q.empty()) q.pop();否则会报错：Runtime error!
//比葫芦画瓢 （高仿 Dungeon Master）
//还是注意分清坐标与行列的关系！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
char s[5], e[5];
int map[10][10];
struct coor {
int x, y;
};
int sx, sy, ex, ey;
queue<coor>q;
int mx[] = { 2,2,1,1,-1,-1,-2,-2 };
int my[] = { 1,-1,2,-2,2,-2,1,-1 };
void bfs() {
while (!q.empty()) {
coor g = q.front();
q.pop();
//if(g.x==ex&&g.y==ey) break;//加上这一句就错了，本来想简化搜索次数。。（暂时不知道为什么！现在先让搜索进行到底！！）
for (int i = 0;i < 8;i++) {
int dx = g.x + mx[i];
int dy = g.y + my[i];
if (dx > 0 && dy > 0 && dx < 9 && dy < 9 && map[dx][dy] == -1) {
map[dx][dy] = map[g.x][g.y] + 1;
coor h;
h.x = dx;h.y = dy;
q.push(h);
}
}
}
cout << "To get from " << s[0] << s[1] << " to " << e[0] << e[1] << " takes " << map[ex][ey] << " knight moves." << endl;
}
int main() {
while (scanf("%s%s", s, e) != EOF) {
memset(map, -1, sizeof(map));
while (!q.empty()) q.pop();//不加这一句会报错：Runtime error，注意每一轮清空队列！！！
sy = s[0] - 'a' + 1;sx = s[1] - '0';// x 竖 y 横！！（分清）
ey = e[0] - 'a' + 1;ex = e[1] - '0';
coor g;
g.x = sx;g.y = sy;
map[sx][sy] = 0;
q.push(g);
bfs();
}
return 0;
}