Problem Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

 

Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend. 

Process to the end of the file.

 

Output

            For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life." 

 

Sample Input

7 8#.#####.#.a#..r.#..#x.....#..#.##...##...#..............

 

Sample Output

13

 

Code

1 #include 
           
             2 #include 
            
              3 using namespace std; 4 #define N 200 5 char map[N + 5][N + 5];     // input matrix 6 int dx[5] = {
         0, 0, 1, -1};  // (dx[i],dy[i]) is point which show the four directories  7 int dy[5] = {
         1, -1, 0, 0}; 8 int n, m; // the input matrix's length and width 9 struct Node10 {11     int x;12     int y;13     int step;14     //it is crucial which make the priority queue sorting by decreasing15     friend bool operator <(const Node a, const Node b)16     {17         return a.step > b.step;18     }19 };20 21 /*22     void dfs(Node b)23     1. push b into the priority queue24     2. when queue is not empty, execute those following codes25         2.1 make the value of the map to be "#", and pop from the queue26         2.2 judge the four directories of the value27             if it's "#", then ignore it.28             else if it's "x", then make step = previous step + 2;29             else if it's ".", make step = previous step + 1;30             if u can find the friend, then jump out.31 */32 void dfs(Node b)33 {34     priority_queue
             
               q;35     int i;36     Node pre, cur;37     q.push(b);38     while (!q.empty())39     {40         pre = q.top();41         q.pop();42         map[pre.x][pre.y] = '#';43         for (i = 0; i < 4; i++)44         {45             cur.x = pre.x + dx[i];46             cur.y = pre.y + dy[i];47             //if it's blocked or out of index, then ingore48             if (map[cur.x][cur.y] == '#' || cur.x < 0 || cur.x >= n || cur.y < 0 || cur.y >= m)49                 continue;50             //make sure what's the step51             else if (map[cur.x][cur.y] == 'x')52                 cur.step = pre.step + 2;53             else if (map[cur.x][cur.y] == '.')54                 cur.step = pre.step + 1;55             //if u can find it, u can stop56             else if (map[cur.x][cur.y] == 'r')57             {58                 printf("%d\n", pre.step + 1);59                 return;60             }61             q.push(cur);62         }63     }64     printf("Poor ANGEL has to stay in the prison all his life.\n");65 }66 void main()67 {68     int i, j;69     Node b;70     while (scanf("%d %d", &n, &m) != EOF)71     {72         //input73         for (i = 0; i < n; i++)74         {75             getchar();76             for (j = 0; j < m; j++)77             {78                 scanf("%c", &map[i][j]);79                 //because 'a' is unique, but the number of 'r' is uncertain  80                 if (map[i][j] == 'a')81                 {82                     b.x = i;83                     b.y = j;84                     b.step = 0;85                 }86             }87         }88         //recall the funciton89         dfs(b);90     }91 }
             
            
           

 

 

 

Idea

The question is using dfs algorithm and priority queue. And, there are a lot of details which should note.

Firstly, when u have pass the point, u can make the point is '#' so that u will not go back.

Secondly, when u input interger, then input char or when u input char in succession, u should use getchar() so that u can remove the enter.  

Thirdly, when u want to use priority queue, u should firstly declare the "friend bool operator <".

 

Recommend

Eddy