总时间限制: 1000ms 内存限制: 65536kB

描述

公主被恶人抓走，被关押在牢房的某个地方。牢房用N × M (N, M ≤ 200)的矩阵来表示。矩阵中的每项可以代表道路（@）、墙壁（#）、和守卫（x）。
英勇的骑士（r）决定孤身一人去拯救公主（a）。我们假设拯救成功的表示是“骑士到达了公主所在的位置”。由于在通往公主所在位置的道路中可能遇到守卫，骑士一旦遇到守卫，必须杀死守卫才能继续前进。
现假设骑士可以向上、下、左、右四个方向移动，每移动一个位置需要1个单位时间，杀死一个守卫需要花费额外的1个单位时间。同时假设骑士足够强壮，有能力杀死所有的守卫。

给定牢房矩阵，公主、骑士和守卫在矩阵中的位置，请你计算拯救行动成功需要花费最短时间。

输入

第一行为一个整数S，表示输入的数据的组数（多组输入）
随后有S组数据，每组数据按如下格式输入
1、两个整数代表N和M, (N, M ≤ 200).
2、随后N行，每行有M个字符。”@“代表道路，”a“代表公主，”r“代表骑士，”x“代表守卫, “#“代表墙壁。

输出

如果拯救行动成功，输出一个整数，表示行动的最短时间。
如果不可能成功，输出Impossible

样例输入

  1. 2
  2. 7 8
  3. #@#####@
  4. #@a#@@r@
  5. #@@#x@@@
  6. @@#@@#@#
  7. #@@@##@@
  8. @#@@@@@@
  9. @@@@@@@@ 
  10. 13 40
  11. @x@@##x@#x@x#xxxx##@#x@x@@#x#@#x#@@x@#@x
  12. xx###x@x#@@##xx@@@#@x@@#x@xxx@@#x@#x@@x@
  13. #@x#@x#x#@@##@@x#@xx#xxx@@x##@@@#@x@@x@x
  14. @##x@@@x#xx#@@#xxxx#@@x@x@#@x@@@x@#@#x@#
  15. @#xxxxx##@@x##x@xxx@@#x@x####@@@x#x##@#@
  16. #xxx#@#x##xxxx@@#xx@@@x@xxx#@#xxx@x#####
  17. #x@xxxx#@x@@@@##@x#xx#xxx@#xx#@#####x#@x
  18. xx##@#@x##x##x#@x#@a#xx@##@#@##xx@#@@x@x
  19. x#x#@x@#x#@##@xrx@x#xxxx@##x##xx#@#x@xx@
  20. #x@@#@###x##x@x#@@#@@x@x@@xx@@@@##@@x@@x
  21. x#xx@x###@xxx#@#x#@@###@#@##@x#@x@#@@#@@
  22. #@#x@x#x#x###@x@@xxx####x@x##@x####xx#@x
  23. #x#@x#x######@@#x@#xxxx#xx@@@#xx#x#####@

样例输出

  1. 13
  2. 7

思路

状态就是骑士走到的位置(r, j). 初始状态就是字符r所在的位置, 目标状态就是字符a所在的位置, 问题就是要从初始状态找到一条到目标状态步数最少的路径. 这是典型的广搜问题.

存放在队列中的元素应该是一个三元组(row, col, times), 记录了状态(row, col)以及走到该状态所花费的时间.

从状态(row, col)可以向四个方向走, 因而可能扩展出4个新状态. 杀死守卫多花一分钟这件事可以如下处理:

  • 要对队列头部的元素(row, col, times)进行扩展时, 如果发现(row, col)位置有首位, 则清除守卫, 并且只扩展出(row, col, times+1)放入队列. 因为进入一个有守卫的位置(row, col)后, 下一步就只能是杀死守卫, 而不能走到别处. 清除守卫就是将地图矩阵(row, col)位置的守卫字符x缓存字符@.

本体有一个细节, 地图存放是从矩阵graphy[1][1]开始的地方, 而我们提前把地图初始化为#, 这等于在地图外围都加了一圈围墙. 这样我们往四个方向扩展的时候就不用担心是否越界了, 反正一定会撞到墙.

代码如下:

  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. using namespace std;
  6. int N, M;
  7. char graph[205][205];
  8. int visited[205][205];
  9. int xAxis[4] = {-1, 1, 0, 0};  // 4 directions of horizontal ordinate 
  10. int yAxis[4] = {0, 0, -1, 1};  // 4 directions of vertical ordinate
  11. typedef struct Node {
  12.     int row;
  13.     int col;
  14.     int time;
  15.     Node(int x, int y, int _time): row(x), col(y), time(_time) {}
  16. }Node;
  17. queue<Node> myQueue;
  19. void BFS(queue<Node>&, Node&);
  21. int main() {
  22.     int rounds;
  23.     cin >> rounds;    
  24.     while( rounds-- ) {
  25.         /* Initialize data */
  26.         memset(visited, 0x0, sizeof(visited));
  27.         memset(graph, '#', sizeof(graph));
  28.         while( !myQueue.empty() )
  29.            myQueue.pop(); 
  31.         /* Read data */
  32.         Node src(0, 0, 0), dst(0, 0, -1);
  33.         cin >> N >> M;
  34.         for(int i = 1; i <= N; i++) {
  35.             for(int j = 1; j <= M; j++) {
  36.                 cin >> graph[i][j];
  38.                 if(graph[i][j] == 'r') {  // Found kinght
  39.                     src.row = i;
  40.                     src.col = j;
  41.                     src.time = 0;
  42.                 }
  43.                 if(graph[i][j] == 'a') {  // Found angel
  44.                     dst.row = i;
  45.                     dst.col = j;
  46.                     dst.time = -1;
  47.                 }
  48.             }
  49.         }
  51.         /* BFS and display result */
  52.         myQueue.push(src);
  53.         visited[ src.row ][ src.col ] = 0x1;
  54.         BFS(myQueue, dst);
  55.     }
  57.     return 0;
  58. }
  60. void BFS(queue<Node>& myQueue, Node& dst) {
  61.     while( !myQueue.empty() ) {
  62.         Node tmpNode = myQueue.front();
  64.         /* Encounter angel */
  65.         if( tmpNode.row == dst.row && tmpNode.col == dst.col ) {
  66.             cout << tmpNode.time << endl;
  67.             return;
  68.         }
  70.         /* Traversal 4 directions */
  71.         if(graph[ tmpNode.row ][ tmpNode.col ] == 'x') {
  72.             graph[ tmpNode.row ][ tmpNode.col ] = '@';    // kill the guard
  73.             myQueue.push( Node(tmpNode.row, tmpNode.col, tmpNode.time+1) );
  74.         }
  75.         else {
  76.             for(int i = 0; i < 4; i++) {
  77.                 int xx = tmpNode.row + xAxis[i];
  78.                 int yy = tmpNode.col + yAxis[i];
  79.                 if (graph[xx][yy] == '#')
  80.                     continue;
  81.                 if ( !visited[xx][yy] ) {
  82.                     myQueue.push( Node(xx, yy, tmpNode.time + 1) );
  83.                     visited[xx][yy] = 0x1;
  84.                 }
  85.             }
  86.         }
  87.         myQueue.pop();
  88.     }
  89.     cout << "Impossible" << endl;
  90. }