题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1372
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.
题意: 骑士环游,给定起点和终点,求出最少步数。
题解:8*8的期盼,可以把各点之间的补数先BFS求出打表,再直接输出就可以。根据棋盘的对称性,可以避免一些重复计算。
AC代码:
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define N 10 using namespace std; int step[N][N][N][N],visit[N][N]; int dir[][2]={ {1,2},{1,-2},{-1,2},{-1,-2}, {2,1},{2,-1},{-2,1},{-2,-1} }; struct Node{ int x,y,s; }; int bfs(int sx,int sy,int ex,int ey) { queue<Node> q; Node head={sx,sy,0}; q.push(head); memset(visit,-1,sizeof(visit)); visit[sx][sy]=0; while(q.size()){ Node f=q.front(); q.pop(); if(f.x==ex&&f.y==ey)return f.s; for(int i=0;i<8;i++){ int dx=dir[i][0]+f.x,dy=dir[i][1]+f.y; if(dx>=0&&dx<8&&dy>=0&&dy<8&&visit[dx][dy]){ visit[dx][dy]=0; Node t={dx,dy,f.s+1}; q.push(t); } } } } int main() { cin.sync_with_stdio(false); memset(step,-1,sizeof(step)); for(int i=0;i<8;i++) for(int j=0;j<8;j++) for(int k=0;k<8;k++) for(int l=0;l<8;l++) if(step[i][j][k][l]!=-1)continue; else if(i==k&&j==l) step[i][j][k][l]=0; else { int temp=bfs(i,j,k,l); step[i][j][k][l]=step[k][l][i][j]=temp; step[j][i][l][k]=step[l][k][j][i]=temp; } char c1,c2; int x1,y2; while(cin>>c1>>x1>>c2>>y2){ printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,x1,c2,y2,step[c1-'a'][x1-1][c2-'a'][y2-1]); } return 0; }
作者: MummyDing
出处:http://blog.csdn.net/mummyding
原文:http://blog.csdn.net/mummyding/article/details/43679277