拯救大兵瑞恩

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 2208 字
状态压缩BFS，格子加上钥匙集合
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1495
// 题意：n*m 迷宫，相邻格之间可能是墙或某类门，格子里可能放钥匙，求从 (1,1) 到 (n,m) 的最短时间，不可达输出 -1。
// 思路：把「所在格子 + 已持有的钥匙集合」压成一个状态做 BFS，门的类型用位掩码判断，第一次到达终点即为最短路。
// 复杂度：O(n*m*2^p) 时间 / O(n*m*2^p) 空间
// 易错点：同一格可能放多把钥匙要用按位或累加；门和墙是双向的，两个方向都要记录，边长 1 且开门拿钥匙不耗时。
#include <bits/stdc++.h>
using namespace std;
const int MAXC = 105;
const int MAXS = 1024;
int door[MAXC][MAXC];
int keyMask[MAXC];
int dista[MAXC][MAXS];
int main(){
    int n, m, p;
    if(!(cin >> n >> m >> p)) return 0;
    for(int i = 0; i < MAXC; i++){
        for(int j = 0; j < MAXC; j++) door[i][j] = -1;
    }
    int k;
    cin >> k;
    for(int i = 0; i < k; i++){
        int x1, y1, x2, y2, g;
        cin >> x1 >> y1 >> x2 >> y2 >> g;
        int a = (x1 - 1) * m + (y1 - 1);
        int b = (x2 - 1) * m + (y2 - 1);
        door[a][b] = g;
        door[b][a] = g;
    }
    int s;
    cin >> s;
    for(int i = 0; i < s; i++){
        int x, y, q;
        cin >> x >> y >> q;
        int a = (x - 1) * m + (y - 1);
        keyMask[a] |= 1 << (q - 1);
    }
    int total = n * m;
    int lim = 1 << p;
    for(int i = 0; i < total; i++){
        for(int j = 0; j < lim; j++) dista[i][j] = -1;
    }
    int start = 0;
    int target = total - 1;
    queue<pair<int, int>> q;
    dista[start][keyMask[start]] = 0;
    q.push({start, keyMask[start]});
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    while(!q.empty()){
        int c = q.front().first;
        int mk = q.front().second;
        q.pop();
        if(c == target){
            cout << dista[c][mk] << '\n';
            return 0;
        }
        int cx = c / m + 1;
        int cy = c % m + 1;
        for(int t = 0; t < 4; t++){
            int nx = cx + dx[t];
            int ny = cy + dy[t];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            int nc = (nx - 1) * m + (ny - 1);
            int g = door[c][nc];
            if(g == 0) continue;
            if(g > 0 && !(mk & (1 << (g - 1)))) continue;
            int nmk = mk | keyMask[nc];
            if(dista[nc][nmk] != -1) continue;
            dista[nc][nmk] = dista[c][mk] + 1;
            q.push({nc, nmk});
        }
    }
    cout << -1 << '\n';
    return 0;
}
拯救大兵瑞恩

正文

一本通·提高篇的其它内容
