1257：Knight Moves
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
输入n代表有个n×n的棋盘，输入开始位置的坐标和结束位置的坐标，问一个骑士朝棋盘的八个方向走马字步，从开始坐标到结束坐标可以经过多少步。
【输入】
首先输入一个n,表示测试样例的个数。
每个测试样例有三行。
第一行是棋盘的大小L(4≤L≤300)；
第二行和第三行分别表示马的起始位置和目标位置(0..L−1)。
【输出】
马移动的最小步数，起始位置和目标位置相同时输出0。
【输入样例】
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
【输出样例】
5
28
0
1
oop!
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. using namespace std; 6. int map[302][302],p[500000][4]; 7. int xx[8]={-2,-2,-1,1,2,2,1,-1}; 8. int yy[8]={-1,1,2,2,1,-1,-2,-2}; 9. int n,m,x1,y1,x2,y2; 10. char ch; 11. void bfs(){ 12. int x,y,t=0,w=1; 13. while(w>t){ 14. t++; 15. for(int i=0;i<8;i++){ 16. x=p[t][1]+xx[i]; 17. y=p[t][2]+yy[i]; 18. if(x>=0&&x<m&&y>=0&&y<m&&map[x][y]==0){ 19. w++;p[w][1]=x;p[w][2]=y; 20. p[w][3]=p[t][3]+1;map[x][y]=1; 21. if(x==x2&&y==y2){ 22. printf("%d\n",p[w][3]);return; 23. } 24. } 25. } 26. } 27. } 28. int main(int argc, char *argv[]) 29. { 30. scanf("%d",&n); 31. for(int k=1;k<=n;k++){ 32. scanf("%d %d %d %d %d",&m,&x1,&y1,&x2,&y2); 33. memset(map,0,sizeof(map)); 34. memset(p,0,sizeof(p)); 35. map[x1][y1]=1;p[1][1]=x1,p[1][2]=y1,p[1][3]=0; 36. if(x1==x2&&y1==y2) printf("0\n"); 37. else bfs(); 38. } 39. return 0; 40. }
