UVa 439 - Knight Moves 搜索专题

439-Knight Moves

13381

56.27%

5157

93.21%

题目链接：

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

样例输入：

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 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做比较好。

求步数时， 有个小技巧， 开个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.\n", 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 LOCAL
    freopen("input.txt", "r", stdin);
#endif
    while(~scanf("%s %s", start, end) && start[0]){
        memset(vis, 0, sizeof(vis));
        bfs();
    }
    return 0;
}