思路
主要做法就是在每个点上面,加一个edge的状态,默认是0,也就是说双向通路,如果是墙我们就变成-1,如果是钥匙,就是大于0的正整数。用0~3来表示4个方向,正好和偏向数组相同。这样写代码会更方便一些。
#include <iostream>
#include <deque>
using namespace std;
int n, m, p, k, s, edges[13][13][4], keys[13][13];
int dx[] {1, 0, -1, 0}, dy[]{0, 1, 0, -1};
bool st[13][13][1030];
struct Node {
int x, y, state, d;
};
int shortest() {
deque<Node> dq;
dq.push_back({1, 1, 0, 0});
while (!dq.empty()) {
auto [x, y, state, d] = dq.front();
dq.pop_front();
if (x == n && y == m) return d;
if (st[x][y][state]) continue;
st[x][y][state] = true;
if ((state | keys[x][y]) != state)
dq.push_front({x, y, state | keys[x][y], d});
for (int i = 0; i < 4; ++i) {
if (edges[x][y][i] == 0 || edges[x][y][i] > 0 && (state & (1 << (edges[x][y][i] - 1)))) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m)
dq.push_back({nx, ny, state, d + 1});
}
}
}
return -1;
}
int main() {
cin >> n >> m >> p >> k;
for (int i = 0; i < k; ++i) {
int x1, y1, x2, y2, g;
cin >> x1 >> y1 >> x2 >> y2 >> g;
for (int j = 0; j < 4; ++j)
if (x1 + dx[j] == x2 && y1 + dy[j] == y2)
edges[x1][y1][j] = edges[x2][y2][(j + 2) % 4] = (g == 0 ? -1 : g);
}
cin >> s;
for (int i = 0; i < s; ++i) {
int x, y, q;
cin >> x >> y >> q;
keys[x][y] |= 1 << (q - 1);
}
int ans = shortest();
cout << ans << endl;
return 0;
}
edges[x1][y1][j] = edges[x2][y2][(j + 2) % 4] = (g == 0 ? -1 : g);
请问一下,这句是什么意思
如果是墙的话,就把这条路标记成-1,表示这条路不通。(j + 2) % 4的意思就是当前方向的下标是j的话,相反方向要么是j + 2, 要么是j - 2。所以直接+2,对4取模就好了。
牛逼
niu