学步园

//典型的BFS（广度优先搜索）<br /> //马走日所需最少步数问题<br /> #include<iostream><br /> using namespace std;<br /> int map[8][8];//记录步数数组<br /> int vis[8][8];//访问过的记录数组<br /> char a[3],b[3];<br /> int x1,y1,x2,y2;<br /> void set(int x1,int y1)<br /> {<br /> //剪去不合理范围<br /> if(x1+1 <= 7 && y1+2 <= 7 && !vis[x1+1][y1+2])<br /> map[x1+1][y1+2] = map[x1][y1]+1;<br /> if(x1+1 <= 7 && y1-2 >= 0 && !vis[x1+1][y1-2])<br /> map[x1+1][y1-2] = map[x1][y1]+1;<br /> if(x1-1 >= 0 && y1+2 <= 7 && !vis[x1-1][y1+2])<br /> map[x1-1][y1+2] = map[x1][y1]+1;<br /> if(x1-1 >= 0 && y1-2 >= 0 && !vis[x1-1][y1-2])<br /> map[x1-1][y1-2] = map[x1][y1]+1;<br /> if(x1+2 <= 7 && y1+1 <= 7 && !vis[x1+2][y1+1])<br /> map[x1+2][y1+1] = map[x1][y1]+1;<br /> if(x1-2 >= 0 && y1+1 <= 7 && !vis[x1-2][y1+1])<br /> map[x1-2][y1+1] = map[x1][y1]+1;<br /> if(x1+2 <= 7 && y1-1 >= 0 && !vis[x1+2][y1-1])<br /> map[x1+2][y1-1] = map[x1][y1]+1;<br /> if(x1-2 >= 0 && y1-1 >= 0 && !vis[x1-2][y1-1])<br /> map[x1-2][y1-1] = map[x1][y1]+1;<br /> }<br /> void search(int x1,int y1,int x2,int y2)<br /> {<br /> int step = 1;<br /> vis[x1][y1] = 1;<br /> set(x1,y1);<br /> //广度优先搜索过程<br /> while(map[x2][y2] == 0)<br /> {<br /> for(int i = 0;i < 8;++i)<br /> for(int j = 0;j < 8;++j)<br /> if(map[i][j] == step)<br /> {<br /> vis[i][j] = 1;<br /> set(i,j);<br /> }<br /> ++step;<br /> }<br /> }<br /> int main()<br /> {<br /> while(cin >> a >> b)<br /> {<br /> memset(map,0,sizeof(map));//初始化<br /> memset(vis,0,sizeof(vis));//初始化<br /> x1 = a[0] - 'a';<br /> y1 = a[1] - '1';<br /> x2 = b[0] - 'a';<br /> y2 = b[1] - '1';<br /> if(strcmp(a,b) == 0)<br /> cout << "To get from "<< a <<" to "<< b << " takes 0 knight moves." <<endl;<br /> else<br /> {<br /> search(x1,y1,x2,y2);<br /> cout << "To get from "<< a <<" to "<< b << " takes "<< map[x2][y2] <<" knight moves." << endl;<br /> }<br /> }<br /> return 0;<br /> }