UVa 439：Knight Moves 搜索专题

UVa 439：Knight Moves 搜索专题2014-10-06 csdn博客 shuangde800题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=380

题目类型：搜索

样例输入：

e2 e4a1 b2b2 c3a1 h8a1 h7h8 a1b1 c3f6 f6

样例输出：

To get from e2 to e4 takes 2 knight moves.To get from a1 to b2 takes 4 knight moves.To get from b2 to c3 takes 2 knight moves.To get from a1 to h8 takes 6 knight moves.To get from a1 to h7 takes 5 knight moves.To get from h8 to a1 takes 6 knight moves.To get from b1 to c3 takes 1 knight moves.To get from f6 to f6 takes 0 knight moves.

分析：

这题也是一道十分经典的搜索入门题。由于题目是指定象棋中马的开始位置，与目标位置，要求马以最少的步数走到目标位置。凡是求最短步数的，一般用BFS做比较好。

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45525.htm

求步数时，有个小技巧，开个vis数组，初始化为0，然后这个用来记录走的步数，而不仅仅是用来标记是否走过。

具体见代码

#include<iostream>#include<cstdio>#include<cstring>using namespace std;char start[3], end[3];int dir[8][2] = {{-2,1},{-1,2},{1,2},{2,1}, {2,-1},{1,-2},{-1,-2},{-2,-1}};int vis[10][10]; struct Node{int x, y; };Node que[1000];void bfs（）{int front=0, rear=1;que[0].x=start[0]-"a", que[0].y=start[1]-"0"-1;vis[que[0].x][que[0].y] = 1;while（front<rear）{Node t = que[front++];// 如果遇到满足条件的，直接输出if（t.x==end[0]-"a" && t.y==end[1]-"0"-1）{ printf（"To get from %s to %s takes %d knight moves.
", start,end,vis[t.x][t.y]-1）;return ;}for（int i=0; i<8; ++i）{int dx=t.x+dir[i][0], dy=t.y+dir[i][1];if（dx>=0 && dx<8 && dy>=0 && dy<8 && ！vis[dx][dy]）{vis[dx][dy] = vis[t.x][t.y]+1;// 记住步数Node temp;temp.x=dx, temp.y=dy;que[rear++] = temp;}}}}int main（）{#ifdef LOCALfreopen（"input.txt", "r", stdin）;#endifwhile（~scanf（"%s %s", start, end） && start[0]）{memset（vis, 0, sizeof（vis））;bfs（）;}return 0;}