理解题意
从网格单元$(1, 1)$到$(N ,M)$的最短路问题: 如果不考虑钥匙🔑和门🚪的限制, 本题就是一个常见的$bfs$
问题. 考虑🔑的限制, 需要加一个维度表示当前有的钥匙集合这一信息.
可以用类似状压$DP$的思路考虑一个带有集合属性的状态.
状压$DP$
状态表示 $d(x, y, s)$
-
集合: 从起点$(1, 1)$到$(x, y)$且所持有钥匙为$s$(二进制表示)的所有路径.
-
属性:
Min
路径长度.
状态计算
正如我们在 AcWing 341. 最优贸易 描述的, 我们可以依据$DP$分析状态而用图算法计算状态. 或者统一来说,
这里采用的思路是: 从集合的角度分析最优问题. 状态计算的思路是考虑当前状态能够更新哪些状态.
$bfs$
状态的计算相比于经典的$bfs$问题, 只是多了一维状态需要考虑:
-
在向相邻格点移动时, 需要判断是否能通过: 如果是🚪判断当前状态是否持有对应🔑.
-
在状态更新时, 我们可以采用
Y总
在视频的思路 — 用当前状态更新相邻格点状态、以及判断当前
格点是否存在🔑, 如果有则更新当前格点的状态. 两种计算的状态权重为$1$和$0$, 所以可以用双端
队列$bfs$求解. -
此外我们可以再用一点贪心的思想: 拿钥匙不会增加所用时间, 并且拥有更多钥匙🔑可能保证我们到达
某个🚪时不需要回头. 也就是拿🔑一定至少不增加所用时间, 很可能会减少所用时间. 所以在状态计算
时, 我们更新格点的同时更新其所持有的钥匙, 这样就不需要在某个格点$(x,y)$时, 需要额外判断是否
要更新同一位置$(x, y)$的持有钥匙的状态, 因为这在之前的状态更新中以及计算过了.每次更新状态, 对于$d(x, y, s)$, 相同的$d$距离值以及相同位置$(x, y)$, 我们只保留$s$持有钥匙最多
的状态, 用它来更新后续状态. 可以证明这样计算的后续状态的距离值相比于最优解不会增加.
代码实现
$bfs$基础上额外考虑一维压缩的状态.
#include <set>
#include <queue>
#include <cstring>
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 11, M = N * N, E = N * N * 4, P = 1 << 10;
int n, m, p, k;
int h[M], e[E], w[E], ne[E], idx;
int id[N][N]; // id[x][y] = x * n + y 二维到一维的映射
int dist[M][P], key[M]; //key[id]: 编号为id的格子中的钥匙状态
set <pii> st; //记录哪些边没有考虑 即可以直接通过的边
void add(int u, int v, int c)
{
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}
void build()
{
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
for( int x = 1; x <= n; x ++ )
for( int y = 1; y <= m; y ++ )
{
for( int i = 0; i < 4; i ++ )
{
int nx = x + dx[i], ny = y + dy[i];
if( !nx || nx > n || !ny || ny > m ) continue;
int a = id[x][y], b = id[nx][ny];
if( !st.count({a, b}) ) add(a, b, 0);
}
}
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[1][key[1]] = 0; //起点(1, 1) 且只计算其钥匙最大的状态
queue<pii> que;
que.push({1, key[1]}); //(id, s)
while( que.size() )
{
pii cur = que.front(); que.pop();
int u = cur.x, s = cur.y;
if( u == id[n][m] ) return dist[u][s];
for( int i = h[u]; ~i; i = ne[i] )
{
int v = e[i], s_ = s | key[v]; //s_ v的钥匙最大状态
if( w[i] && !(s & w[i]) ) continue; //需要钥匙 而没有对应钥匙
if( dist[v][s_] > dist[u][s] + 1 )
{
dist[v][s_] = dist[u][s] + 1;
que.push({v, s_});
}
}
}
return -1;
}
int main()
{
cin >> n >> m >> p >> k;
for( int i = 1, t = 1; i <= n; i ++ )
for( int j = 1; j <= m; j ++ )
id[i][j] = t ++;
memset(h, -1, sizeof h);
while( k -- )
{
int x1, y1, x2, y2, t;
cin >> x1 >> y1 >> x2 >> y2 >> t;
int a = id[x1][y1], b = id[x2][y2];
st.insert({a, b}); st.insert({b, a}); //记录在集合中
if( t ) add(a, b, 1 << (t - 1)), add(b, a, 1 << (t - 1));
//t - 1使得🔑标号从0开始而不是从1开始
}
cin >> k; //输入哪些格子有🔑
while( k -- )
{
int x, y, t;
cin >> x >> y >> t;
int a = id[x][y];
key[a] |= ( 1 << (t - 1));
}
build(); //加入没有输入的 可以直接通过的边
cout << bfs() << endl;
return 0;
}