首页 > 代码库 > A计划
A计划
A计划
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 26 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。 现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中只能前后左右移动,每移动一格花1时刻。层间的移动只能通过时空传输机,且不需要任何时间。
Input
输入的第一行C表示共有C个测试数据,每个测试数据的前一行有三个整数N,M,T。 N,M迷宫的大小N*M(1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况,后N*M表示迷宫第二层的布置情况。
Output
如果骑士们能够在T时刻能找到公主就输出“YES”,否则输出“NO”。
Sample Input
1 5 5 14 S*#*. .#... ..... ****. ...#. ..*.P #.*.. ***.. ...*. *.#..
Sample Output
YES
Source
HDU 2007-6 Programming ContestView Code
1 #include <stdio.h> 2 #include <stdlib.h> 3 int Len_X,Len_Y,D,SIGN; 4 char Map[20][20][5]; 5 int DFS(int x,int y,int z,int d,int D) 6 { 7 int ii,jj; 8 if(SIGN==1)return 0; 9 if(x>=Len_X||x<0||y>=Len_Y||y<0||d>D)return 0; 10 if(d<=D&&Map[x][y][z]==‘P‘){SIGN=1;return 1;} 11 if(Map[x][y][z]==‘#‘) 12 { 13 if(z==0&&(Map[x][y][1]!=‘*‘&&Map[x][y][1]!=‘#‘)) 14 { 15 DFS(x,y,1,d,D);Map[x][y][1]=‘.‘;return 0; 16 } 17 else if(z==1&&(Map[x][y][0]!=‘*‘&&Map[x][y][0]!=‘#‘)) 18 { 19 DFS(x,y,0,d,D);Map[x][y][0]=‘.‘;return 0; 20 } 21 else return 0; 22 } 23 if(d>=D)return 0; 24 if(Map[x][y][z]==‘*‘)return 0; 25 else Map[x][y][z]=‘*‘; 26 /* getch(); 27 putchar(‘\n‘); 28 printf("\tStyp: %d\n",d); 29 for(ii=0;ii<Len_X;ii++) 30 { 31 if(z==1)putchar(‘\t‘); 32 for(jj=0;jj<Len_Y;jj++) 33 { 34 printf("%c",Map[ii][jj][z]); 35 } 36 putchar(‘\n‘); 37 }*/ 38 if(x+1<Len_X&&Map[x+1][y][z]!=‘*‘) 39 { 40 DFS(x+1,y,z,d+1,D); 41 if(Map[x+1][y][z]!=‘#‘) 42 Map[x+1][y][z]=‘.‘; 43 } 44 if(x-1>=0&&Map[x-1][y][z]!=‘*‘) 45 { 46 DFS(x-1,y,z,d+1,D); 47 if(Map[x-1][y][z]!=‘#‘) 48 Map[x-1][y][z]=‘.‘; 49 } 50 if(y+1<Len_Y&&Map[x][y+1][z]!=‘*‘) 51 { 52 DFS(x,y+1,z,d+1,D); 53 if(Map[x][y+1][z]!=‘#‘) 54 Map[x][y+1][z]=‘.‘; 55 } 56 if(y-1>=0&&Map[x][y-1][z]!=‘*‘) 57 { 58 DFS(x,y-1,z,d+1,D); 59 if(Map[x][y-1][z]!=‘#‘) 60 Map[x][y-1][z]=‘.‘; 61 } 62 return 0; 63 } 64 65 int main() 66 { 67 int Begin_x,Begin_y,Begin_z,i,j,T; 68 scanf("%d",&T); 69 while(T--) 70 { 71 scanf("%d%d%d",&Len_X,&Len_Y,&D); 72 getchar(); 73 for(i=0;i<Len_X;i++) 74 { 75 for(j=0;j<Len_Y;j++) 76 { 77 scanf("%c",&Map[i][j][0]); 78 if(Map[i][j][0]==‘S‘) 79 {Begin_x=i;Begin_y=j;Begin_z=0;} 80 } 81 getchar(); 82 } 83 getchar(); 84 for(i=0;i<Len_X;i++) 85 { 86 for(j=0;j<Len_Y;j++) 87 { 88 scanf("%c",&Map[i][j][1]); 89 if(Map[i][j][1]==‘S‘) 90 {Begin_x=i;Begin_y=j;Begin_z=1;} 91 } 92 getchar(); 93 } 94 SIGN=0; 95 DFS(Begin_x,Begin_y,Begin_z,0,D); 96 if(SIGN==1) 97 printf("YES\n"); 98 else 99 printf("NO\n"); 100 } 101 return 0; 102 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。