最短路 + 状态压缩
集合角度
从格点(1,1)->格点(n,m), 如果没有条件限制可以简单用BFS求解.
加上钥匙和门的限制后, 简单用坐标表示点的状态不能处理遇到门时的判断, 所以我们需要增加一维表示
当前状态的钥匙信息.
类似状压DP的集合角度:
状态表示
集合 : d[x,y,s], 从起点(1,1)到格点(x,y)且已有钥匙为s的所有路线. 这里s用状态压缩保存钥匙信息.
属性 : 所有路线的最小值
状态计算
我们用当前状态能够更新哪些状态的方式计算状态, 这种方式更加契合最短路的更新方式.
更新方式 :
1. (x,y)有钥匙, 拿钥匙没有时间损耗, 能拿则拿. (x,y,s)->(x,y,s|key)
2. 4个方向转移
2.1 无门/有墙
2.2 有门 : 判断当前状态是否有对应钥匙
实现算法
双端队列BFS :
(x,y)有钥匙时, 更新(x,y,s|key)的权重为0, 在同一个格点不同的状态.
到其他格点相同钥匙状态权重为1
BFS
这里可以再加上一个贪心思路 : 同一格点(x,y)具有相同距离dist, 那么用钥匙更多的状态更新
后续状态得到的最终结果一定不大于钥匙更少状态更新的后续状态. 所以我们在到达其他结点时可以只
保存钥匙更多的状态, 也就是只保留权重为1的状态转移.
具体实现
为方便描述状态, 将格点坐标(x,y)通过编号变为一维.
题目只输入有墙/门的边, 所以我们需要建立无门的边. 可以先保存有墙/门的边, 最后遍历所有可能的边,
如果未输入该边, 说明这是一条无门的边.
双端队列
#include <iostream>
#include <cstring>
#include <deque>
#include <set>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 11, M = N * N, E = 400, P = 1 << 10, INF = 0x3f3f3f3f;
int n, m, p, k;
int h[M], e[E], w[E], ne[E], idx;
int g[N][N]; //(x,y)->id
int dist[M][P], key[M]; //格点+状态的距离 / 格点钥匙
bool st[M][P]; //是否出队
set<pii> edges; //格点(u-v)是否在输入中
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[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
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 u = g[x][y], v = g[nx][ny];
if( edges.count({u,v}) == 0 ) add(u, v, 0); //直接通过的边
}
}
}
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
int start = g[1][1];
dist[start][0] = 0;
deque<pii> que;
que.push_front({start,0});
while( que.size() )
{
pii cur = que.front(); que.pop_front();
int u = cur.x, s = cur.y;
if( st[u][s] ) continue;
st[u][s] = true;
if( key[u] )
{//格点有钥匙
int s_ = s | key[u];
if( dist[u][s_] > dist[u][s] )
{
dist[u][s_] = dist[u][s];
que.push_front({u,s_});
}
}
for( int i = h[u]; ~i; i = ne[i] )
{
int v = e[i], c = w[i];
if( !c || (s & (1 << c -1 )) )
{//可以直接通过 / 有对应钥匙
if( dist[v][s] > dist[u][s] + 1 )
{
dist[v][s] = dist[u][s] + 1;
que.push_back({v,s});
}
}
}
}
int res = INF, end = g[n][m];
for( int s = 0; s < (1<<p); s++ ) res = min( res, dist[end][s] );
if( res == INF ) res = -1;
return res;
}
int main()
{
cin >> n >> m >> p >> k;
for( int i = 1, id = 1; i <= n; i++ )
for( int j = 1; j <= m; j++ )
g[i][j] = id ++;
memset(h, -1, sizeof h);
while( k -- )
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int u = g[x1][y1], v = g[x2][y2];
edges.insert({u,v}); edges.insert({v,u});
if( c )
{//有门边
add(u, v, c); add(v, u, c);
}
}
build(); //构建可以直接通过的边
int s;
cin >> s;
while( s -- )
{//钥匙
int x, y, q;
cin >> x >> y >> q;
int u = g[x][y];
key[u] |= 1 << q - 1; //用 += 可能出错
}
cout << bfs() << endl;
return 0;
}
BFS
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
const int N = 11, M = N * N, E = 400, P = 1 << 10;
int n, m, p, k;
int id[N][N]; //(x,y) -> id
int g[M][M]; //邻接矩阵
int dist[M][P], key[M];
int bfs()
{
memset(dist, 0x3f, sizeof dist);
int start = id[1][1], end = id[n][m];
dist[start][0] = 0;
queue<pii> que;
que.push({start,0});
while( que.size() )
{
pii cur = que.front(); que.pop();
int u = cur.x, s = cur.y;
if( u == end ) return dist[end][s];
int x = (u + m - 1) / m, y = (u - 1) % m + 1;//id->(x,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 v = id[nx][ny];
if( g[u][v] == -1 ) continue; //墙
if( g[u][v] && !(s >> g[u][v] -1 & 1 ) ) continue; //无对应钥匙
int s_ = s | key[v]; //能拿钥匙则拿
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 ++;
while( k -- )
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int u = id[x1][y1], v = id[x2][y2];
if( c ) g[u][v] = g[v][u] = c;
else g[u][v] = g[v][u] = -1;//-1表示有墙 0默认值表示可以直接通过
}
int s;
cin >> s;
while( s -- )
{
int x, y, q;
cin >> x >> y >> q;
int u = id[x][y];
key[u] |= 1 << q - 1;
}
cout << bfs() << endl;
return 0;
}