POJ 2312 Battle City 【BFS + 优先队列】

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

题目源于网络

---

题意

用英文字符 ‘Y’ ‘T’ ‘S’ ‘R’ ‘B’ ‘E’ 分别表示 “你（起点）” “目标（终点）” “钢砖（不可破坏）” “河流（不可经过）” “普通砖（可摧毁，时间+2）” “空地（直接经过，时间+1）”，要求求得从起始位置到终点的最短耗时。

解析

类似最短路问题，考虑BFS,但这里要求不是路径最短，而是耗时最短，此时可以采用优先队列保存路径，始终先行耗时最短路径。

#include<iostream>
#include<math.h>
#include <algorithm>
#include<stdio.h>
#include<string.h>
#include<stack> 
#include<queue>
using namespace std;
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define req(i, a, b) for(int i=(a); i<=(b); i++)
#define ull unsigned __int64
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pf printf
#define prk printf("\n")
#define pi acos(-1.0)
#define ms(a,b) memset((a),(b),sizeof((a)))
#define mc(a,b) memcpy((a),(b),sizeof((a))) 
#define w while
#define vr vector<int>
typedef long long ll;
//如果不考虑耗时，那就显然是一道最基础BFS的题目
//现在要耗时最少，其实就相当于每次要走的路径都进行排序之前路径耗时
//优先选择耗时最短的先走，最后选择耗时最短的输出，这个排序过程可用优先队列完成

struct acm{
    int x;
    int y;
    int time;
}; 

char a[305][305];
bool f[305][305];
int n, m;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = { 0, 1,-1, 0};

bool operator < (acm x, acm y)
{
    return x.time > y.time;
}

bool bfs(int x, int y)
{
    priority_queue<acm> q;
    acm fi, se;
    f[x][y] = 1;
    fi.x = x;
    fi.y = y;
    fi.time = 0;
    q.push(fi);
    w(!q.empty())
    {
        acm s;
        se = q.top();
        q.pop();
        if(a[se.x][se.y] == 'T')
        {
            pr(se.time);
            return true;
        }
        req(i, 0, 3)
        {
            s.x = se.x + dx[i];
            s.y = se.y + dy[i];
            if(s.x >= 1 && s.y >=1 && s.x <= n && s.y <= m && (a[s.x][s.y] != 'S' && a[s.x][s.y] != 'R') && !f[s.x][s.y])
            {
                f[s.x][s.y] = 1;
                s.time = se.time + 1;
                if(a[s.x][s.y] == 'B')
                s.time++;
                q.push(s);
            }
        }
    }
    return false;
}

int main()
{
    int x, y;
    w(sc2(n, m) && n && m)
    {

        ms(f, false);
        req(i, 1 ,n)
        {
            getchar();
            req(j, 1, m)
            {

                scanf("%c",&a[i][j]);
                if(a[i][j] == 'Y')
                x = i, y = j;
            }
        }   
        if(!bfs(x, y))
        pf("-1\n");
    }
    return 0;
}