dfs与bfs A计划

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

解题思路：

将原始地图简化。

解题代码：广搜

View Code

  1 // File Name: /media/文档/源程序/实验室/4A.cpp
  2 // Author: sheng
  3 // Created Time: 2013年03月14日 星期四 18时37分41秒
  4 
  5 #include <iostream>
  6 #include <string.h>
  7 using namespace std;
  8 
  9 #define Max 20
 10 
 11 int tag[2][Max][Max];
 12 int rear, top, X, Y, C, n, m;
 13 const int x_add[] = {0, 0, -1, 1};
 14 const int y_add[] = {1, -1, 0 ,0};
 15 char maze[2][Max][Max];
 16 
 17 struct node
 18 {
 19     int c;
 20     int x;
 21     int y;
 22     int step;
 23 }sign[2 * Max * Max + 1];
 24 
 25 void remake()
 26 {
 27     for(int i = 0 ; i < n ; i++)
 28     {
 29         for(int j = 0 ; j < m ; j++)
 30         {
 31             char &a = maze[0][i][j] , &b = maze[1][i][j] ;
 32             if(a=='#' && b=='#')
 33                 a = b = '*' ;
 34             else if((a=='#' && b=='*')||(a=='*' && b=='#'))
 35                 a = b = '*' ;
 36         }
 37     }
 38 }
 39 
 40 int bfs(int num)
 41 {
 42     int x, y, c, s;
 43     x = y = c = s = 0;
 44 //    cout << X <<" " << Y <<" " <<C<<endl;
 45     sign[rear++] = (node){c, x, y, s};
 46     while(rear > top)
 47     {
 48         /*
 49         cout <<"       c = " <<sign[top].c << "x = "<<sign[top].x <<"y = "<<sign[top].y<<endl;
 50         cout <<"       step = "<<sign[top].step<<endl;
 51         cout <<"       <<   "<<maze[sign[top].c][sign[top].x][sign[top].y] <<"     >>"<<endl;
 52         cout <<"       rear = "<<rear  <<"top = "<<top<<endl<<endl;
 53         */
 54         if(sign[top].c == C && sign[top].x == X && sign[top].y == Y && sign[top].step <= num)
 55             return 1;
 56         int c1 = sign[top].c;
 57         int x1 = sign[top].x;
 58         int y1 = sign[top].y;
 59         int s1 = sign[top++].step;
 60         if (maze[c1][x1][y1] == '#' && !tag[!c1][x1][y1])
 61         {
 62             tag[c1][x1][y1] = 1;
 63             sign[rear++] = (node){!c1, x1, y1, s1};
 64             continue;
 65         }
 66         for (int i = 0; i < 4; i ++)
 67         {
 68             int xx = x1 + x_add[i];
 69             int yy = y1 + y_add[i];
 70             if (xx >= n || yy >= m || xx < 0 || yy < 0)
 71                 continue;
 72             if ( maze[c1][xx][yy] != '*' && !tag[c1][xx][yy])
 73             {
 74                 tag[c1][xx][yy] = 1;
 75                 sign[rear].c = c1;
 76                 sign[rear].x = xx;
 77                 sign[rear].y = yy;
 78                 sign[rear++].step = s1 + 1;
 79             }
 80         }
 81     }
 82     return 0;
 83 }
 84 
 85 int main ()
 86 {
 87     int t;
 88     int i, j;
 89     int num;
 90     cin >> t;
 91     while (t--)
 92     {
 93         memset(maze, 0 , sizeof (maze));
 94         memset(tag, 0, sizeof (tag));
 95         rear = top = 0;
 96         cin >> n >> m >> num;
 97         for (i = 0; i < n; i ++)
 98         {
 99             for (j = 0; j < m; j ++)
100             {
101                 cin >> maze[0][i][j];
102                 if(maze[0][i][j] == 'P')
103                 {
104                     X = i;
105                     Y = j;
106                     C = 0;
107                 }
108             }
109         }
110         for (i = 0; i < n; i ++)
111         {
112             for (j = 0; j < m; j ++)
113             {
114                 cin >> maze[1][i][j];
115                 if (maze[1][i][j] == 'P')
116                 {
117                     X = i;
118                     Y = j;
119                     C = 1;
120                 }
121             }
122         }
123         remake();
124         if (bfs(num))
125             cout << "YES" << endl;
126         else  cout << "NO" << endl;
127     }
128     return 0;
129 }