HDU 5025 – Saving Tang Monk [优先队列BFS]

点击打开vjudge题目链接

题意:给定一个N×N矩阵,从K走到T,其中有几个钥匙,有蛇,有的点不能走。经过蛇时必须杀掉并且消耗时间1,钥匙有M个编号,得到编号i的钥匙之前必须得到i~i-1的钥匙。问最少需要时间从K走到T.

分析:维护一个优先队列BFS即可,头一次做四维vis的…

C++代码:

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

struct Node{
    int x, y, d, key, kill;
    Node(int x, int y, int d, int key, int kill):x(x), y(y), d(d), key(key), kill(kill) {}
    bool operator < (const Node & rhs) const {
        return d > rhs.d;
    }
};
const int maxn = 105;
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char mat[maxn][maxn];
int N, M;
int no[maxn][maxn];
bool vis[maxn][maxn][10][1<<5];

inline bool in(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N && mat[x][y] != '#';
}
int BFS(int x, int y) {
    memset(vis, 0, sizeof(vis)); vis[x][y][0][0] = true;
    priority_queue<Node> qu; qu.push(Node(x, y, 0, 0, 0));
    while(!qu.empty()) {
        Node u = qu.top(); qu.pop();
        for (int i = 0; i < 4; ++i) {
            Node v(u.x+dir[i][0], u.y+dir[i][1], u.d+1, u.key, u.kill);
            if(!in(v.x, v.y) || vis[v.x][v.y][v.key][v.kill]) continue;
            vis[v.x][v.y][v.key][v.kill] = true;
            if(mat[v.x][v.y] == 'S') {
                if(!(v.kill & (1<<no[v.x][v.y]))) {
                    v.d += 1;
                    v.kill |= (1<<no[v.x][v.y]);
                }
                qu.push(v);
            }
            else if(v.key + 1 == mat[v.x][v.y] - '0') {
                v.key += 1;
                qu.push(v);
            }
            else if(mat[v.x][v.y] == 'T' && v.key == M)
                return v.d;
            else qu.push(v);
        }
    }
    return -1;
}

int main() {
    while(~scanf("%d%d", &N, &M), N||M) {
        int cnt = 0, x, y;
        memset(no, 0, sizeof(no));
        for(int i = 0; i < N; ++i) {
            scanf("%s", mat[i]);
            for (int j = 0; j < N; ++j) {
                if(mat[i][j] == 'S') no[i][j] = cnt++;
                if(mat[i][j] == 'K') x = i, y = j;
            }
        }
        int b = BFS(x, y);
        if(b == -1) puts("impossible");
        else printf("%d\n", b);
    }
    return 0;
}

欢迎留言