|
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
 View Code
1 #include <stdio.h> 2 #include <queue> 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 Node 10 { 11 int x; 12 int y; 13 int step; 14 //it is crucial which make the priority queue sorting by decreasing 15 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 queue 24 2. when queue is not empty, execute those following codes 25 2.1 make the value of the map to be "#", and pop from the queue 26 2.2 judge the four directories of the value 27 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<Node> 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 ingore 48 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 step 51 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 stop 56 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 //input 73 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 funciton 89 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
|
