Rescue

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42470    Accepted Submission(s): 14546


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
题解：
    这题，讲的就是拯救天使的故事，拯救天使，拯救天使，emmm,谁是天使，就是'a',
    但是，题和实际很相似呀，毕竟是天使诶！  angel  ！！！当然有很多英雄去拯救她啦😍，
    所以在进行搜索的时候，就可以让法力无边的' angel '   神行  去找她的朋友‘ r '.找到离她最近的" r "即可，这需要注意一下。
    然后就是优先队列，bfs,遇到士兵步数+2；
代码：
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string.h>
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
int n,m;
char ma[205][205];
int vis[220][220];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int ex,ey;
struct node
{
        int x,y,step;
        friend bool operator<(node a,node b)
        {    
                return a.step>b.step;     } }; bool check(int x,int y)
        {
        if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==0&&ma[x][y]!='#')
                return 1;
        return 0;
}
int bfs(int x,int y)
{
        priority_queue<node> q;    
        node now,next;
        now.x=x;
        now.y=y;    
        now.step=0;
        vis[now.x][now.y]=1;
        q.push(now);    
        while(!q.empty())
        {    
                now=q.top();        
                 q.pop();    
                if(ma[now.x][now.y]=='r')
                {        
                        return now.step;
                }         
                for(int i=0;i<4;i++)
                {        
                        next.x=now.x+dir[i][0];
                        next.y=now.y+dir[i][1];
                        if(check(next.x,next.y))
                        {                      
                                if(ma[next.x][next.y]=='x')
                                {            
                                         vis[next.x][next.y]=1;
                                        next.step=now.step+2;
                                        q.push(next);
                                }                
                                else
                               {
                                        vis[next.x][next.y]=1;
                                        next.step=now.step+1;
                                        q.push(next);
                               }
                     }
              }
        }    
        return -1;
}
int main ()
{
        while(cin>>n>>m)
        {    
                getchar();
                memset(vis,0,sizeof(vis));
                for(int i=0;i<n;i++)
                {
                        for(int j=0;j<m;j++)
                        {
                                cin>>ma[i][j];
                                if(ma[i][j]=='a')
                                {         
                                        ex=i;ey=j;    
                                }    
                       }    
                        getchar();        
                  }
                    int ans=bfs(ex,ey);
                    if(ans==-1)
                    cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
                    else
                    cout<<ans<<endl;
        }    
        return 0;
｝

Battle City

Problem Description
Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now.

What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers, steel walls and brick walls only. Your task is to get a bonus as soon as possible suppose that no enemies will disturb you (See the following picture).

Your tank can't move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?
Input
The input consists of several test cases. The first line of each test case contains two integers M and N (2 <= M, N <= 300). Each of the following M lines contains N uppercase letters, each of which is one of 'Y' (you), 'T' (target), 'S' (steel wall), 'B' (brick wall), 'R' (river) and 'E' (empty space). Both 'Y' and 'T' appear only once. A test case of M = N = 0 indicates the end of input, and should not be processed.
Output
For each test case, please output the turns you take at least in a separate line. If you can't arrive at the target, output "-1" instead.
Sample Input 
3 4
YBEB
EERE
SSTE
0 0
Sample Output 
8
题解：
    这题，就是把拯救天使改成找目标，吃金币，然后把士兵变成砖墙，
代码： 
#include <stdio.h> #include <algorithm> #include <math.h> #include <set> #include <queue> #include <stack> #include <map> #include <string.h> #include <iostream> #include <vector> #include <functional> using namespace std; int m,n; char ma[305][305]; bool vis[305][305]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int ex,ey; struct node
{ int x,y,step; friend bool operator<(node a,node b)
    {  return a.step>b.step;
    }
}; bool check(int x,int y) {  if(x>=0&&x<m&&y>=0&&y<n&&vis[x][y]==0&&ma[x][y]!='S'&&ma[x][y]!='R') return 1; return 0;
} int bfs(int x,int y) {
    priority_queue<node> q;
    node now,next;
    now.x=x;
    now.y=y;
    now.step=0;
    vis[now.x][now.y]=1;
    q.push(now);  while(!q.empty())
    {
        now=q.top();
        q.pop();  if(ma[now.x][now.y]=='T')
        {  return now.step;
        }  for(int i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];  if(check(next.x,next.y))
            { if(ma[next.x][next.y]=='B')
                {
                    vis[next.x][next.y]=1;
                    next.step=now.step+2;
                    q.push(next);
                }  else {
                    vis[next.x][next.y]=1;
                    next.step=now.step+1;
                    q.push(next);
                }
            }
        }
    }  return -1;
} int main() {  while(~scanf("%d%d",&m,&n))
    {
        getchar();  if(m==0&&n==0) break;  memset(vis,0,sizeof(vis));  for(int i=0;i<m;i++)
        {  for(int j=0;j<n;j++)
            { scanf("%c",&ma[i][j]);  if(ma[i][j]=='Y')
                {
                    ex=i;
                    ey=j;
                }
            }
            getchar();
        } printf("%d\n",bfs(ex,ey));
    } return 0;
}