解题思路:BFS
1)马的跳跃方向
在国际象棋的棋盘上，一匹马共有8个可能的跳跃方向，如图1所示，按顺时针分别记为1~8，设置一组坐标增量来描述这8个方向；
2)基本过程
设当前点(i,j)，方向k，沿方向k跳一步后的新点(newi,newj)；每走一步，都要判断新点(newi,newj)是否还在棋盘上：
若1£newi£8且1£newj£8，则新点仍在棋盘上，则还需判断该点是否已经走过，即
若visited[newi][newj]=0，表示该步可走；
若visited[newi][newj]=1，表示该点已经走过，不能再走，放弃当前方向，并转向下一个方向试探；
否则，直接放弃当前方向，并转向下一个方向试探；
本题其实BFS的模板题。照着模板写就是了。。。。
代码如下:
/*
* 1372_1.cpp
*
* Created on: 2013年8月15日
* Author: Administrator
*/ #include <iostream>
#include <queue> using namespace std; char str1[5],str2[5]; const int maxn = 100;
bool visited[maxn][maxn]; //*
int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}}; struct State{
int x;
int y;
int step_counter;
}; bool checkState(State st){ //*
if(!visited[st.x][st.y]&&(!(st.x <0 ||st.x >= 8 ||st.y <0 ||st.y >=8))){
return true;
} return false;
} int bfs(){ queue<State> q;
State st;
State now ,next;
int x_e,y_e; //*
st.x = str1[1] - '1';
st.y = str1[0] - 'a';
st.step_counter = 0;
x_e = str2[1] - '1';
y_e = str2[0] - 'a'; q.push(st);
memset(visited,0,sizeof(visited));
visited[st.x][st.y] = 1;
while(!q.empty()){
now = q.front(); if(now.x == x_e && now.y == y_e){
return now.step_counter;
}
int i;
for(i = 0 ; i < 8 ; ++i){
next.x = now.x + dir[i][0];
next.y = now.y + dir[i][1];
next.step_counter = now.step_counter + 1; if(checkState(next)){
q.push(next);
visited[next.x][next.y] = 1;
}
}
q.pop(); } return -9;
} int main(){ int ans;
while(scanf("%s%s",str1,str2)!=EOF){
ans = bfs();
printf("To get from %s to %s takes %d knight moves.\n",str1,str2,ans);
}
}