AcWing 1131. 拯救大兵瑞恩
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。
瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。
迷宫的外形是一个长方形，其南北方向被划分为 N 行，东西方向被划分为 M 列， 于是整个迷宫被划分为 N×M 个单元。
每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。
南北或东西方向相邻的 2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。
注意： 门可以从两个方向穿过，即可以看成一条无向边。
迷宫中有一些单元存放着钥匙，同一个单元可能存放 多把钥匙，并且所有的门被分成 P 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即 (N,M) 单元里，并已经昏迷。
迷宫只有一个入口，在西北角。
也就是说，麦克可以直接进入 (1,1)单元。
另外，麦克从一个单元移动到另一个相邻单元的时间为 1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。
输入格式
第一行有三个整数,分别表示 N,M,P 的值。
第二行是一个整数 k，表示迷宫中门和墙的总数。
输出格式
输出麦克营救到大兵瑞恩的最短时间。
如果问题无解，则输出 -1。
数据范围
思路
分层图最短路。将每个点划分为几个状态，状态的划分由走到当前点拥有哪些钥匙决定。
d[i][j] 表示走到 i 这个点且当前拥有钥匙的状态为 j 的最短距离。
每次bfs 到一个新的点时，判断点之间是否有门， 如果有的话是否有钥匙，然后如果能通过的话，更新邻点的最短距离。
如果当前走到的点有钥匙因为捡钥匙代价为0，所以能捡就捡，并且更新下拥有的钥匙的状态。
代码
// Author：zzqwtcc // Problem: C - Swiss-System Tournament // Contest: AtCoder - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） // Time：2021-10-09 20:00:14 // URL: https://atcoder.jp/contests/abc222/tasks/abc222_c // Memory Limit: 1024 MB // Time Limit: 2000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 90 + 10; int n, m, p; int mp[20][20]; vector<PII>vec[110]; set<PII>edges; int key[105]; bool vis[105][1 << 10 + 1]; int d[105][1 << 10 + 1]; int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }; void build() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { for (int k = 0; k < 4; ++k) { int x = i + dx[k]; int y = j + dy[k]; if (!x || x > n || !y || y > m)continue; if (edges.count({ mp[i][j],mp[x][y] }) == 0) { vec[mp[i][j]].push_back({ mp[x][y],0 }); } } } } } int bfs() { deque<PII>q; q.push_back({ 1,0 }); memset(vis, 0, sizeof vis); memset(d, 0x3f, sizeof d); d[1][0] = 0; while (q.size()) { auto t = q.front(); q.pop_front(); if (vis[t.first][t.second])continue; vis[t.first][t.second] = true; //因为是 bfs 所以第一次遍历到当前点就是其最短距离 if (t.first == n * m)return d[t.first][t.second]; // 如果当前点有钥匙，因为捡钥匙是没有花费的，所以能捡就捡 if (key[t.first]) { // 更新拥有钥匙的状态 int state = t.second | key[t.first]; // 更新新状态的最短距离 if (d[t.first][state] > d[t.first][t.second]) { d[t.first][state] = d[t.first][t.second]; q.push_front({ t.first,state }); } } // 遍历当前点能到的所有点 for (int i = 0; i < vec[t.first].size(); ++i) { int j = vec[t.first][i].first; // 邻点的编号 int m = vec[t.first][i].second;// 与邻点之间是否有不可通过的门 // 如果有且没有打开这扇门的钥匙，就 continue if (m && !(t.second >> m & 1))continue; // 更新当前点的最短距离 if (d[j][t.second] > d[t.first][t.second] + 1) { d[j][t.second] = d[t.first][t.second] + 1; q.push_back({ j,t.second }); } } } return -1; } void solve() { cin >> n >> m >> p; int t = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { mp[i][j] = ++t; } } int k; cin >> k; while (k--) { int x1, y1, x2, y2, g; cin >> x1 >> y1 >> x2 >> y2 >> g; int a = mp[x1][y1], b = mp[x2][y2]; edges.insert({ a,b }); edges.insert({ b,a }); if (g) { vec[a].push_back({ b,g }); vec[b].push_back({ a,g }); } } build(); int s; cin >> s; while (s--) { int x, y, q; cin >> x >> y >> q; key[mp[x][y]] |= 1 << q; } cout << bfs() << endl; } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
