HDU 1242/ZOJ 1649 – Rescue [最短路]

Link

http://acm.hdu.edu.cn/showproblem.php?pid=1242

http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=1649

Problem

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.)

Mean

给一个N*M的图,知道Angel(r)和他的朋友(a)的位置,Angel的朋友要拯救Angel,求从r到a的最短移动距离,如果路上经过警察则距离多1。

Analysis

这道题可以类似于dijkstra那样做,因为经过警察后入队列后的优先级是不一样的,这样可以用优先队列取出优先级最高(最短)的继续bfs,用一个数组存到各点的最短路。

注意有一点比较坑,题意说可能会有多个警察。

Code

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int x, y, time;
    Node(int x, int y, int time):x(x), y(y), time(time) {}
    bool operator < (const Node & rhs) const {
        return time > rhs.time;
    }
};
const int maxn = 220, inf = 0x3f3f3f3f;
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int N, M, stx, sty, edx, edy;
int d[maxn][maxn];
char v[maxn][maxn];

inline bool in(int x, int y) {
    return x >= 1 && x <= N && y >= 1 && y <= M && v[x][y] != '#';
}

void dijkstra() {
    memset(d, inf, sizeof(d));
    d[stx][sty] = 0;
    priority_queue<Node> qu;
    qu.push(Node(stx, sty, 0));

    while(!qu.empty()) {
        Node u = qu.top(); qu.pop();
        if(d[u.x][u.y] < u.time)
            continue;
        for(int i = 0; i < 4; ++i) {
            Node to(u.x + dir[i][0], u.y + dir[i][1], u.time + 1);
            if(!in(to.x, to.y)) continue;
            if(v[to.x][to.y] == 'x')
                to.time += 1;
            if(d[to.x][to.y] > to.time) {
                qu.push(to);
                d[to.x][to.y] = to.time;
            }
        }
    }
}

int main() {
    while(~scanf("%d%d", &N, &M)) {
        gets(v[0]);
        for(int i = 1; i <= N; ++i) {
            gets(v[i] + 1);
            for(int j = 1; j <= M; ++j) {
                if(v[i][j] == 'r')
                    stx = i, sty = j;
                if(v[i][j] == 'a')
                    edx = i, edy = j;
            }
        }
        dijkstra();
        if(d[edx][edy] >= inf) puts("Poor ANGEL has to stay in the prison all his life.");
        else printf("%d\n", d[edx][edy]);
    }
    return 0;
}

欢迎留言