首页 > 代码库 > 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 Contest
  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 }
View Code