输入输出样例

输入

输出

题意：

(原题太长我就不贴了，简单叙述一下)
一个N*M的迷宫，每个单元格之间可能有门或者墙，也可能啥也没有。门和墙的总数为K（会读入墙和门的位置坐标）
门存在种类，只有拥有对应种类的钥匙才可以打开这类门
钥匙的总量为S（会读入钥匙的坐标）
从一个单元格到另一个单元格时间为1
现在从左上角（1,1）出发，到右下角（N，M）,最少花费多少时间？
针对样例，看图分析

紫色为钥匙
橙色为墙或者门的种类
绿色为线路

题解：

这就是网络流吗？爱了爱了
迷宫的题一般用BFS就可以做
有了钥匙我们就状压+BFS
状态压缩钥匙，是为了方便记录每一把钥匙的状态
就比如当前状态是“100”，说明我有第三把钥匙，因为第三位（从右往左）是1，而“100”对应的是4，你会发现你拥有第i把钥匙，状态就是2^i-1(十进制下)，这样我们就可以用二进制来存储钥匙信息
key|=Key [ x ] [ y ] //就是将当前已有钥匙的状态给key
我们在开门时验证自己有钥匙的方式：
( mp [x] [y] [u.x] [u.y] & key ) ! = mp [x] [y] [u.x] [u.y]
[x][y]表示当前单元格，[u.x][u.y]表示上一个单元格
mp就表示两个单元格之间门的编号，也可能是墙（表示方式和钥匙一样），直接与钥匙&运算，如果运算后还是本身，说明有指定的钥匙（因为有钥匙说明那一位为1,1&1=1，还是本身，如果没有指定钥匙，说明那一位是0，0&1=0，值就发生改变）

然后就是bfs的走迷宫过程，走迷宫有四种状态要continue
1.如果超格子了
2.如果撞墙了
3.如果遇到门但是木有钥匙
4.之前走过了

坑点：
1.钥匙可以重复使用而非用过即毁
2.一个地方可以存放多个钥匙，所以保存钥匙时不要将前一个覆盖掉
3.初始点也可以放钥匙
4.存在走不通的情况记得输出-1

代码：

代码中注释非常详细

#include<bits/stdc++.h>
using namespace std;
const int dx[]={
   1,-1,0,0};//增量数组
const int dy[]={
   0,0,1,-1};
int vis[25][25][40005],x,y,xx,yy,p,pw[105],mp[16][16][16][16],Key[20][20],n,m,tot;
struct nod{
   int x,y,key,stp;}q[5000005];//q为广搜用的队列
int bfs(){
   
	int h=1,t=1;
	vis[1][1][Key[1][1]]=1;//一开始就有位于(1,1)的钥匙
	q[t]=(nod){
   1,1,Key[1][1],0};
	for(;h<=t;++h){
   
		nod u=q[h];//取队头
		for(int k=0;k<4;++k){
   
			int x=u.x+dx[k];
			int y=u.y+dy[k];
			int key=u.key;//已有钥匙 
			int stp=u.stp;//已走步数 
			if(x<1||y<1||x>n||y>m)continue;//如果超出格子则跳过
			if(mp[x][y][u.x][u.y]==-1)continue;//如果两个格子之间有墙则跳过
			if((mp[x][y][u.x][u.y]&key)!=mp[x][y][u.x][u.y])continue;//如果两个格子之间有门而且手上所有的钥匙里没有能打开该门的钥匙则跳过
			key|=Key[x][y];//更新已有钥匙的情况 
			if(vis[x][y][key])continue;//如果之前搜到过这个状态则跳过
			vis[x][y][key]=1;stp++;//可以则扩展
            q[++t]=(nod){
   x,y,key,stp};//保存当前坐标，以及钥匙与步伐情况 
			if(x==n&&y==m)return stp;//如果已经走到(n,m)则返回答案
		}
	}
	return -1;//无法抵达
}
int main(){
   
	pw[1]=1;for(int i=2;i<=15;++i)pw[i]=pw[i-1]<<1;//预处理pw数组
	 
	scanf("%d%d%d",&n,&m,&p);
	scanf("%d",&tot);
	while(tot--){
   
		scanf("%d%d%d%d%d",&x,&y,&xx,&yy,&p);
		if(p==0){
   
			mp[x][y][xx][yy]=mp[xx][yy][x][y]=-1;
		}
		else {
   
			mp[x][y][xx][yy]=mp[xx][yy][x][y]=pw[p];//将门的标号更新到指定位置 
		}
	}
	int q; 
	scanf("%d",&tot);
	while(tot--){
   
		scanf("%d%d%d",&x,&y,&q);
		Key[x][y]|=pw[q];//表示在(x,y)点上有编号为q的钥匙,将钥匙的编号更新到指定坐标 
	}
	cout<<bfs();
	return 0;
}

这个题我就用两个字形容：绝了
很久没有遇到这么好的题

P4011 孤岛营救问题

文章目录

输入输出样例

题意：

题解：

代码：