BFS
题意：给你棋盘上两点的坐标，按照中国象棋中马的走法，求出其最短的步数。
// File Name: 1073.cpp
// Author: bo_jwolf
// Created Time: 2014年02月03日 星期一 21时24分46秒
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<queue>
using namespace std;
int dir[ 15 ][ 5 ] = { { -2, 1 }, { -1, 2 }, { -2, -1 }, { -1, -2 },{ 2, 1 },{ 1, 2 }, { 2, -1 }, { 1, -2 } };
const int maxn = 1005;
int vis[ maxn ][ maxn ], sx, sy, ex, ey, Step = 0;
struct node{
int x, y, step;
}edge[ maxn ];
void Bfs(){
queue< node > Q;
node temp, p, q;
temp.x = sx;
temp.y = sy;
vis[ sx ][ sy ] = 1;
temp.step = 0;
Q.push( temp );
if( sx == ex && sy == ey ){
Step = 0;
return;
}
while( !Q.empty() ){
p = Q.front();
Q.pop();
for( int i = 0; i < 8; ++i ){
int y = p.y + dir[ i ][ 0 ];
int x = p.x + dir[ i ][ 1 ];
if( x >= 0 && y >= 0 && x < 8 && y < 8 && !vis[ x ][ y ] ){
q.x = x;
q.y = y;
q.step = p.step + 1;
if( x == ex && y == ey ){
Step = q.step;
return;
}
vis[ x ][ y ] = 1;
Q.push( q );
}
}
}
}
int main(){
char str1[ maxn ], str2[ maxn ];
while( scanf( "%s %s", str1, str2 ) == 2 ){
sx = str1[ 0 ] - ‘a‘;
sy = str1[ 1 ] - ‘1‘;
ex = str2[ 0 ] - ‘a‘;
ey = str2[ 1 ] - ‘1‘;
memset( vis, 0, sizeof( vis ) );
Bfs();
printf( "To get from %s to %s takes %d knight moves.\n", str1, str2, Step );
}
return 0;
}