HDOJ_ACM_A计划

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

Idea

For this question, using flags[][], which mark wheather u passed or not, using dfs find the shortest path. U should care about more details, such as using flag to mark whether u find it, using outOfTime to mark whether the time is used up.

Code

View Code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <queue>
  4 using namespace std;
  5 #define N 10
  6 #define M 10
  7 struct Position
  8 {
  9     int x;
 10     int y;
 11     int step;
 12     int floornum;
 13 };
 14 struct
 15 {
 16     char map[N + 2][M + 2];
 17     int flags[N + 2][M + 2];
 18 }floors[2];
 19 int dx[5] = {1, -1, 0, 0};
 20 int dy[5] = {0, 0, 1, -1};
 21 int main()
 22 {
 23     int c, n, m, t, flag, outOfTime, floornum, result, i, j;
 24     Position source, des, pre, cur;
 25     scanf("%d", &c);
 26     while (c--)
 27     {
 28         queue<Position> q;
 29         scanf("%d %d %d", &n, &m, &t);
 30         getchar();
 31         for (floornum = 0; floornum < 2; floornum++)
 32         {
 33             for (i = 0; i < n; i++)
 34             {
 35                 //input
 36                 scanf("%s", floors[floornum].map[i]);
 37                 //initialize
 38                 for (j = 0; j < m; j++)
 39                     floors[floornum].flags[i][j] = 0;
 40             }
 41         }
 42         //printf("input successfully\n");
 43         source.x = 0;
 44         source.y = 0;
 45         source.step = 0;
 46         source.floornum = 0;
 47         q.push(source);
 48         flag = 0;        //mark whether find it or not
 49         outOfTime = 0;   //mark whether the time is used up or not
 50         floors[0].map[0][0] = 1;
 51         //printf("go to queue\n");
 52         while (!q.empty() && !flag && !outOfTime)
 53         {
 54             pre = q.front();
 55             q.pop();
 56             //printf("pop(): x = %d, y = %d, floornum = %d, step = %d\n", pre.x, pre.y, pre.floornum, pre.step);
 57             for (i = 0; i < 4; i++)
 58             {
 59                 //get the current
 60                 cur.x = pre.x + dx[i];
 61                 cur.y = pre.y + dy[i];
 62                 cur.step = pre.step + 1;
 63                 cur.floornum = pre.floornum;
 64                 //out of index
 65                 if (cur.x < 0 || cur.x >= n || cur.y < 0 || cur.y >= m)
 66                     continue;
 67                 //if the position has passed
 68                 if (floors[cur.floornum].flags[cur.x][cur.y] == 1)
 69                     continue;
 70                 //out of time
 71                 if (cur.step > t)
 72                 {
 73                     outOfTime = 1;
 74                     break;
 75                 }
 76                 //go the other floor
 77                 if (floors[cur.floornum].map[cur.x][cur.y] == '#')
 78                 {
 79                     floors[cur.floornum].flags[cur.x][cur.y] = 1;
 80                     cur.floornum = 1 - cur.floornum;
 81                 }
 82                 if (floors[cur.floornum].map[cur.x][cur.y] == 'P')
 83                 {
 84                     flag = 1;
 85                     result = cur.step;
 86                     break;
 87                 }
 88                 //
 89                 else if (floors[cur.floornum].map[cur.x][cur.y] == '.')
 90                 {
 91                     floors[cur.floornum].flags[cur.x][cur.y] = 1;
 92                     q.push(cur);
 93                     //printf("push(): x = %d, y = %d, floornum = %d, step = %d\n", cur.x, cur.y, cur.floornum, cur.step);
 94                 }
 95             }
 96         } 
 97         if (flag == 0)
 98             printf("NO\n");
 99         else if (outOfTime == 1)
100             printf("NO\n");
101         else if (flag == 1 && outOfTime == 0)
102             printf("YES\n");
103     }
104     system("pause");
105     return 0;
106 }