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

公主被绑架了，你有迷宫的地图，该迷宫只有两层楼#表示楼梯，.表示空地，*表示墙，第一行输入N,M,K,表示需要输入两个N*M的矩阵地图，起始点为S，公主的位置为P，问你能否在限定的K步之内，找到公主。如果能的话输出YES,否则输出NO.

HDU 2007-6 Programming Contest

 #include <stdio.h>

 #include <stdlib.h>

 int Len_X,Len_Y,D,SIGN;

 char Map[][][];

 int DFS(int x,int y,int z,int d,int D)

 {

     int ii,jj;

     if(SIGN==)return ;

     if(x>=Len_X||x<||y>=Len_Y||y<||d>D)return ;

     if(d<=D&&Map[x][y][z]=='P'){SIGN=;return ;}

     if(Map[x][y][z]=='#')

     {

         if(z==&&(Map[x][y][]!='*'&&Map[x][y][]!='#'))

         {

             DFS(x,y,,d,D);Map[x][y][]='.';return ;

         }

         else if(z==&&(Map[x][y][]!='*'&&Map[x][y][]!='#'))

         {

             DFS(x,y,,d,D);Map[x][y][]='.';return ;

         }

         else return ;

     }

         if(d>=D)return ;

     if(Map[x][y][z]=='*')return ;

     else Map[x][y][z]='*';

   /* getch();

     putchar('\n');

     printf("\tStyp: %d\n",d);

             for(ii=0;ii<Len_X;ii++)

             {

                 if(z==1)putchar('\t');

                 for(jj=0;jj<Len_Y;jj++)

                 {

                     printf("%c",Map[ii][jj][z]);

                 }

                 putchar('\n');

             }*/

     if(x+<Len_X&&Map[x+][y][z]!='*')

     {

         DFS(x+,y,z,d+,D);

         if(Map[x+][y][z]!='#')

             Map[x+][y][z]='.';

     }

     if(x->=&&Map[x-][y][z]!='*')

     {

         DFS(x-,y,z,d+,D);

         if(Map[x-][y][z]!='#')

             Map[x-][y][z]='.';

     }

     if(y+<Len_Y&&Map[x][y+][z]!='*')

     {

         DFS(x,y+,z,d+,D);

         if(Map[x][y+][z]!='#')

             Map[x][y+][z]='.';

     }

     if(y->=&&Map[x][y-][z]!='*')

     {

         DFS(x,y-,z,d+,D);

         if(Map[x][y-][z]!='#')

             Map[x][y-][z]='.';

     }

     return ;

 }

 int main()

 {

     int Begin_x,Begin_y,Begin_z,i,j,T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d",&Len_X,&Len_Y,&D);

             getchar();

             for(i=;i<Len_X;i++)

             {

                 for(j=;j<Len_Y;j++)

                 {

                     scanf("%c",&Map[i][j][]);

                     if(Map[i][j][]=='S')

                     {Begin_x=i;Begin_y=j;Begin_z=;}

                 }

                 getchar();

             }

             getchar();

             for(i=;i<Len_X;i++)

             {

                 for(j=;j<Len_Y;j++)

                 {

                     scanf("%c",&Map[i][j][]);

                     if(Map[i][j][]=='S')

                     {Begin_x=i;Begin_y=j;Begin_z=;}

                 }

                 getchar();

             }

             SIGN=;

             DFS(Begin_x,Begin_y,Begin_z,,D);

             if(SIGN==)

                 printf("YES\n");

             else

                 printf("NO\n");

         }

     return ;

 }

修改：2015.5.8

 #include <stdio.h>

 #include <stdlib.h>

 int Len_X,Len_Y,D,SIGN;

 int Begin_x,Begin_y,Begin_z;

 char Map[][][];

 void DFS(int x,int y,int z,int d,int D)

 {

    // printf("\t%d %d %d\n",x,y,z);

     if(SIGN==)return ;

     if(d>D)return ;

     if(Map[x][y][z]=='*')return;

     if(d<=D&&Map[x][y][z]=='P'){SIGN=;return ;}

     if(Map[x][y][z]=='#')

     {

         Map[x][y][z]='*';

         if(z==)DFS(x,y,,d,D);

         else DFS(x,y,,d,D);

         Map[x][y][z]='#';

     }

     else if(Map[x][y][z]=='.')

     {

         Map[x][y][z]='*';

         DFS(x-,y,z,d+,D);

         DFS(x+,y,z,d+,D);

         DFS(x,y-,z,d+,D);

         DFS(x,y+,z,d+,D);

         Map[x][y][z]='.';/*和步数有关，需要点还原*/

     }

     return ;

 }

 void Input(int z)/*输入地图*/

 {

     int i,j;

     for(i=;i<=Len_X+;i++)

     {

         for(j=;j<=Len_Y+;j++)

         {

             if(i==||j==||i==Len_X+||j==Len_Y+){Map[i][j][z]='*';}

             else

             {

                 scanf(" %c",&Map[i][j][z]);

                 if(Map[i][j][]=='S')

                 {

                     Map[i][j][]='.';

                     Begin_x=i;Begin_y=j;Begin_z=;

                 }

             }

         }

     }

     return ;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d",&Len_X,&Len_Y,&D);

         Input();Input(); SIGN=;

         DFS(Begin_x,Begin_y,Begin_z,,D);

         if(SIGN==) printf("YES\n");

         else printf("NO\n");

         }

     return ;

 }

No

A计划

A计划