题目链接: https://www.acwing.com/problem/content/1133/
思路:
利用动态规划分析:
状态转移:
边权只有 $0$ 和 $1$,利用双端队列求最短路!
细节处理:
① 将 $(x,y)$ 代表的点编号 从左到右,从上到下
② 门的处理为双向边,且边权为门类型,门类型最大范围是10种,即可以用 $01$ 二进制表示是否选中,$1$ 表示选中,$0$ 表示未选
③ 用 set
存储边集
④ 输入的钥匙类型要减 $1$ ,即 $0-2^{10}$
⑤ 边的数量
对于竖直的边每行有 n - 1
个,一共 $n$ 行,每条边最大为双向穿过,横向边和竖直边一样 就是 n*(n-1)*2*2 = 400
代码有详细注释:
#include <iostream>
#include <cstring>
#include <deque>
#include <set>
using namespace std;
typedef pair<int,int> PII;
const int N = 11,M = N * N,E = 400,P = 1 << 10;
int h[M],e[E],ne[E],w[E],idx;
int g[N][N]//记录点(x,y)的编号
int key[M];//每个点的钥匙的状态
int dist[M][P];//点编号,点状态
bool st[M][P];
set<PII> edge;//记录边集
int n,m,p,k;
void add(int a,int b,int c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void build()//当G为0时,有一道不可逾越的墙
{
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
for(int i = 1;i <= n;i++)//枚举所有点
{
for(int j = 1;j <= m;j++)
{
for(int u = 0;u < 4;u++)//枚举所有点的上下左右四个方向
{
int a = i + dx[u],b = j + dy[u];
if(a < 1 || a > n || b < 1 || b > m) continue;
int x = g[i][j],y = g[a][b];//(i,j)是源点编号x,(a,b)是目标点编号y,即x -> y
if(!edge.count({x,y})) add(x,y,0);//从x->y建墙,即不能走,边权为0
}
}
}
}
int bfs()
{
memset(dist,0x3f,sizeof dist);
dist[1][0] = 0;//从1号点开始走,状态为0,到1号点距离为0
deque<PII> q;
q.push_back({1,0});
while(q.size())
{
auto t = q.front();
q.pop_front();
int ver = t.first,state = t.second;
if(st[ver][state]) continue;
st[ver][state] = true;
if(ver == n * m) return dist[ver][state];//到达终点(n,m)
if(key[ver])//该点有钥匙
{
int newstate = key[ver] | state;//更新状态
if(dist[ver][newstate] > dist[ver][state])//新状态的距离大于旧状态
{
dist[ver][newstate] = dist[ver][state];//更新距离
q.push_front({ver,newstate});//捡钥匙,未移动,边权为0,从队头加入
}
}
for(int i = h[ver];~i;i = ne[i])
{
int j = e[i];
if(w[i] && !(state >> w[i] - 1 & 1)) continue;//扩展节点且新节点有门我的钥匙(state)开不了门w[i],就跳过
if(dist[j][state] > dist[ver][state] + 1)//否则就判断能否更新距离
{
dist[j][state] = dist[ver][state] + 1;
q.push_back({j,state});//若能更新,则移动,边权为1,从队尾加入
}
}
}
return -1;
}
int main()
{
cin>>n>>m>>p>>k;
memset(h,-1,sizeof h);
for(int i = 1,t = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
g[i][j] = t++;//将所有点从左到右,从上到下,从大到小编号
}
}
while(k--)
{
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;//(x1,y1)->(x2,y2)的钥匙类型(门类型)
int a = g[x1][y1],b = g[x2][y2];
edge.insert({a,b}),edge.insert({b,a});//向边集加入双向边a->b,b->a
if(c) add(a,b,c),add(b,a,c);//如果有门,建边
}
build();//筑墙
int s;
cin>>s;
while(s--)
{
int x,y,state;
cin>>x>>y>>state;
key[g[x][y]] |= 1 << state - 1; //存储钥匙状态
}
cout<<bfs()<<endl;
return 0;
}