跳马问题（算法作业）

#

实验五 跳马问题

###问题描述与实验目的： 给定8*8方格棋盘，求棋盘上一只马从一个位置到达另一位置的最短路径长。 注意马是走“日”形的。

###输入 输入有若干测试数据。 每组测试数据仅1行，每行上有2个方格pos1、pos2，之间用一个空格隔开，每格方格表示棋盘上的一个位置，该位置由表示列的1个字母（a-h）及表示行的一个数字（1-8）构成，如“d7”表示第4列第7行。 ###输出 对输入中每行上的2个方格pos1、pos2，输出马从位置pos1跳到pos2所需的最短路径长。如“a1==>a2: 3 moves”表示从位置a1跳到a2所需的最少步数是3。 注意：按输出样例所示格式输出，如“a1==>a2: 3 moves”中冒号后有一个空格，再跟着所需的最少步数。 ###输入样例 a1 a2 a1 a3 a1 h8 g2 b8

###输出 a1==>a2: 3 moves a1==>a3: 2 moves a1==>h8: 6 moves g2==>b8: 5 moves

##分析： 因为只有8x8的方格，所以考虑bfs搜索即可。

###运行结果：

###源代码：

#include <bits/stdc++.h> using namespace std; const int maxn=100; int mp[10][10]; int dx[8]={1,1,2,2,-1,-1,-2,-2},dy[8]={2,-2,1,-1,2,-2,1,-1}; int ex,ey; int ans; bool check(int x,int y) { return x>=1&&x<=8&&y>=1&&y<=8; } void bfs(int x,int y) { int step=0; queue<tuple<int,int,int>> que; que.push(make_tuple(x,y,0)); while(que.empty()==0) { tuple<int,int,int> tmp=que.front(); que.pop(); for(int i=0;i<8;i++) { int nx=get<0>(tmp); int ny=get<1>(tmp); nx+=dx[i],ny+=dy[i]; int st=get<2>(tmp); if(check(nx,ny)) { que.push(make_tuple(nx,ny,get<2>(tmp)+1)); if(nx==ex&&ny==ey) { ans=st+1; return; } } } } } string s1,s2; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif while(cin>>s1>>s2) { int sx=s1[0]-'a'+1; int sy=s1[1]-'0'; ex=s2[0]-'a'+1,ey=s2[1]-'0'; bfs(sx,sy); cout<<s1<<"==>"<<s2<<": "<<ans<<"moves"<<endl; } return 0; }

实验体会

本次实验非常简单，直接bfs爆力搜索即可。