# 题目

image-20210320104759568

# 题意

从 (1,1) 出发走到 (n,m),途中有墙有门有钥匙,问最短几步走到右下角。

# 思路

利用状态压缩,用二进制位表示第几种钥匙是否持有,利用 BFS 爆搜,再开一个数组储存状态来记忆化剪枝

实现方法有很多种,可以利用邻接表建边,可以直接利用 Next 数组表示下一个位置,邻接表利用空间换取了时间,表示墙和门时如果不用邻接表,则需要用 map<pair<int,int>,pair<int,int>> 这种结构来表示,而邻接表可以用边权来表示,但都是可以过的

# CODE1 (优先队列)

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
typedef pair<int,int> pii;
struct node{
	int x1,y1,x2,y2;
};
struct Node{
	int x,y,d,z;
	bool operator<(const Node &o) const{
		return d>o.d;
	}
};
int n,m,k,p,s;
int Next[4][2]=<!--swig0-->;
int key[11][11];
map<pair<pii,pii>,int> wal,dor;
bool vis[20][20][1<<10];
priority_queue<Node> q;
int bfs(int x,int y){
	int tmp=0;
	if(key[x][y]) tmp=key[x][y];
	q.push({x,y,0,tmp});
	while(!q.empty()){
		Node fr=q.top();
		q.pop();
		if(fr.x==n && fr.y==m) return fr.d;
		if(vis[fr.x][fr.y][fr.z]) continue;
		vis[fr.x][fr.y][fr.z]=1;
		for(int i=0;i<4;i++){
			int nx=fr.x+Next[i][0];
			int ny=fr.y+Next[i][1];
			if(nx<1 || nx>n || ny<1 || ny>m) continue;
			if(wal[<!--swig1-->]) continue;
			if(dor[<!--swig2-->] && ((fr.z>>(dor[<!--swig3-->]-1))&1)==0) continue;
			int now=0;
			if(key[nx][ny]) now=key[nx][ny];
			q.push({nx,ny,fr.d+1,fr.z|now});
		}
	}
	return -1;
}
int main(){
	ios;
	cin>>n>>m>>p>>k;
	while(k--){
		int x1,y1,x2,y2,G;
		cin>>x1>>y1>>x2>>y2>>G;
		if(G==0){
			wal[<!--swig4-->]=1;
			wal[<!--swig5-->]=1;
		}
		else{
			dor[<!--swig6-->]=G;
			dor[<!--swig7-->]=G;
		}
	}
	cin>>s;
	for(int i=1;i<=s;i++){
		int x,y,g;
		cin>>x>>y>>g;
		key[x][y]|=(1<<g-1);
	}
	int ans=bfs(1,1);
	cout<<ans<<'\n';
	return 0;
}

# CODE2 (dis 数组)

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define first x
#define second y
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int MAXN=1e6+100;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const int SUB=-0x3f3f3f3f;
const double eps=1e-4;
const double E=exp(1);
const double pi=acos(-1);
struct node{
	int x,y,state;
};
int n,m,p,k;
int key[11][11],dis[11][11][1<<10];
int Next[4][2]={1,0,0,1,-1,0,0,-1};
bool st[11][11][1<<10];
set<pair<pii,pii>> wal;
map<pair<pii,pii>,int> dor;
deque<node> dq;
int bfs(int x,int y){
	memset(dis,0x3f,sizeof dis);
	dq.push_back({x,y,0});
	dis[x][y][0]=0;
	while(!dq.empty()){
		node now=dq.front();
		dq.pop_front();
		if(now.x==n && now.y==m) return dis[n][m][now.state];
		if(st[now.x][now.y][now.state]) continue;
		st[now.x][now.y][now.state]=1;
		if(key[now.x][now.y]){
			if(dis[now.x][now.y][key[now.x][now.y]|now.state]>dis[now.x][now.y][now.state]){
				dis[now.x][now.y][ key[now.x][now.y] | now.state]=dis[now.x][now.y][now.state];
			}
			now.state|=key[now.x][now.y];
		}
		for(int i=0;i<4;i++){
			int nx=now.x+Next[i][0];
			int ny=now.y+Next[i][1];
			if(nx<1 || nx>n || ny<1 || ny>m) continue;
			if(wal.count(<!--swig8-->)) continue;
			if(dor[<!--swig9-->] && (( 1<<(dor[<!--swig10-->]-1) ) & now.state)==0) continue;
			if(dis[nx][ny][now.state]>dis[now.x][now.y][now.state]+1){
				dis[nx][ny][now.state]=dis[now.x][now.y][now.state]+1;				
				dq.push_back({nx,ny,now.state});
			}
		}
	}
	return -1;
}
int main(){
	ios;
	cin>>n>>m>>p>>k;
	while(k--){
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		if(c){
			dor[<!--swig11-->]=c;
			dor[<!--swig12-->]=c;
		}
		else{
			wal.insert(<!--swig13-->);
			wal.insert(<!--swig14-->);
		}
	}
	int s;
	cin>>s;
	for(int i=1;i<=s;i++){
		int x,y,g;
		cin>>x>>y>>g;
		key[x][y]|=( 1<< g-1);
	}
	int ans=bfs(1,1);
	cout<<ans<<'\n';
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝