骑士移动

发布时间:2016-12-8 22:20:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"骑士移动",主要涉及到骑士移动方面的内容,对于骑士移动感兴趣的同学可以参考一下。

点击打开链接 Play again TimeLimit: 1 Second   MemoryLimit: 32 Megabyte Totalsubmit: 104   Accepted: 23   Description Everyone knows the "knight move" problem. Today you are going to simulate the game again. Providing the length M of a side of the square board and some cells that you can not move the knight into, given the starting postion and the ending postion, find the shortest path you move the knight from the starting postion to the ending postion. If no path can be found, print "No solution" instead. We put a number into the cells. The number begins with 1 and ends with M*M. For example a board of 4*4, the numbers put in the cells are as following: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Input The input contains multiple test cases begining with a integer T(the number of test cases). Each case consists of three parts . Part 1 contains only a integer M(M<=100, the length of a side of the board). Part 2 consists of the starting postion(Xs,Ys) and the ending postion(Xe,Ye) follow. (1<=Xs,Ys,Xe,Ye<=M) Part 3 begins with a integer N, the number of position that you can not move the knight into, followed by N*2 integers, every two representing a position. Output For each test case, print the shortest path that you can move the knight from the begining position to the ending position. The outputs are not the coordinate of a postion but the number in the postion. If more than one path are found, output the smallest number sequence. For example, given a 4*4 board, the starting position is (3,2) and the ending position is (2,3) you can find two shortest path (10, 16, 7) and (10, 1, 7). You shouldn't print (10, 16, 7) but (10, 1, 7) instead. Sample Input 2 4 3 4 3 2 4 4 4 2 1 4 1 3 3 4 1 1 4 4 3 3 3 3 4 4 3 Sample Output 12 3 10 1 7 16 主要是如何记录移动步骤。其中的最优解是通过搜索方向设定的。 #include<stdio.h> #include<string.h> #include<stdlib.h> int map[110][110]; int visit[110][110]; int way[1000]; int dir[8][2] = {-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1}; typedef struct{ int x,y; int step; int pre; }Queue; Queue queue[500010]; int main(){ int T; int i,j; int n,m; int a,b; int t,w; int sx,sy,ex,ey; scanf("%d",&T); while(T--){ scanf("%d",&n); scanf("%d%d%d%d",&sx,&sy,&ex,&ey); scanf("%d",&m); memset(map,0,sizeof(map)); memset(visit,0,sizeof(visit)); while(m--){ scanf("%d%d",&a,&b); map[a][b] = 1; } t = w = 1; queue[t].x = sx; queue[t].y = sy; queue[t].step = 0; queue[t].pre = 0; visit[sx][sy] = 1; while(t<=w && !visit[ex][ey]){ int t1 = queue[t].x; int t2 = queue[t].y; for(i=0;i<8;i++){ int t3 = t1 + dir[i][0]; int t4 = t2 + dir[i][1]; if(t3>0 && t3<=n && t4>0 && t4<=n && !visit[t3][t4]){ w++; visit[t3][t4] = 1; queue[w].x = t3; queue[w].y = t4; queue[w].step = queue[t].step + 1; queue[w].pre = t; } if(t3 == ex && t4 == ey) break; } t++; } if(t<=w){ int cnt = 0; while(w){ way[cnt++] = n*(queue[w].x-1) + queue[w].y; w = queue[w].pre; } for(i=cnt-1;i>=0;i--){ if(i==0) printf("%d\n",way[i]); else printf("%d ",way[i]); } } else printf("No solution\n"); } return 0; }

上一篇:MyEclipse中导入项目时出现乱码的解决方案
下一篇:linux命令

相关文章

关键词: 骑士移动

相关评论