只用BFS的代码
C++ 代码
#include<bits/stdc++.h>
#define PII pair<int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1e2+10;
int a[N][N], idx;
int n, m, p;
int k, s;
vector<PII> g[N];
map<PII, int> edges;
int key[N];
int fx[] = {-1, 1, 0, 0};
int fy[] = {0, 0, -1, 1};
int dis[N][1 << 11];
int vis[N][1 << 11];
void bfs() {
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
dis[1][key[1]] = 0;
queue<PII> q;
q.push({1, key[1]});
vis[1][key[1]] = 1;
while(!q.empty()) {
int u = q.front().fi, st = q.front().se;
q.pop();
//cout<<g[u].size()<<"\n";
for(int i = 0; i < g[u].size();i++) {
int v = g[u][i].fi, t = g[u][i].se;
if(vis[v][st|key[v]]) continue;
int state = st | key[v];
if(t == 0) {
//cout<<u<<" "<<v<<" "<<dis[u][st] + 1;
dis[v][st | key[v]] = dis[u][st] + 1;
q.push({v, st | key[v]});
vis[v][st|key[v]] = 1;
} else {
if(state >> (t - 1) & 1) {
//cout<<u<<" "<<v<<" "<<dis[u][st] + 1;
dis[v][st | key[v]] = dis[u][st] + 1;
q.push({v, st | key[v]});
vis[v][st|key[v]] = 1;
} else {
continue;
}
}
}
}
}
int main() {
cin>>n>>m>>p;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
a[i][j] = ++idx;
}
}
cin>>k;
for(int i = 1;i <= k;i++) {
int x, y, xx, yy, gg;
cin>>x>>y>>xx>>yy>>gg;
if(gg != 0) {
g[a[x][y]].pb({a[xx][yy], gg});
g[a[xx][yy]].pb({a[x][y], gg});
}
edges[{a[x][y],a[xx][yy]}] = 1;
edges[{a[xx][yy], a[x][y]}] = 1;
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
for(int k = 0;k < 4;k++) {
int x = i + fx[k], y = j + fy[k];
if(x < 1||x > n||y < 1||y > m) continue;
if(edges[{a[i][j],a[x][y]}]) continue;
//cout<<a[i][j]<<" "<<a[x][y]<<"\n";
g[a[i][j]].pb({a[x][y], 0});
}
}
}
cin>>s;
for(int i = 1;i <= s;i++) {
int x, y, q;
cin>>x>>y>>q;
key[a[x][y]] |= 1 << q - 1;
//cout<<key[a[x][y]]<<"\n";
}
bfs();
int ans = 0x3f3f3f3f;
for(int i = 0;i < 1 << p;i++) {
ans = min(dis[a[n][m]][i], ans);
}
if(ans == 0x3f3f3f3f) cout<<"-1\n";
else cout<<ans;
return 0;
}