题目

image-20210320104759568

题意

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

思路

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

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

CODE1(优先队列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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]={{1,0},{0,1},{-1,0},{0,-1}};
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[{{fr.x,fr.y},{nx,ny}}]) continue;
			if(dor[{{fr.x,fr.y},{nx,ny}}] && ((fr.z>>(dor[{{fr.x,fr.y},{nx,ny}}]-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[{{x1,y1},{x2,y2}}]=1;
			wal[{{x2,y2},{x1,y1}}]=1;
		}
		else{
			dor[{{x1,y1},{x2,y2}}]=G;
			dor[{{x2,y2},{x1,y1}}]=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数组)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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({{now.x,now.y},{nx,ny}})) continue;
			if(dor[{{now.x,now.y},{nx,ny}}] && (( 1<<(dor[{{now.x,now.y},{nx,ny}}]-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[{{x1,y1},{x2,y2}}]=c;
			dor[{{x2,y2},{x1,y1}}]=c;
		}
		else{
			wal.insert({{x1,y1},{x2,y2}});
			wal.insert({{x2,y2},{x1,y1}});
		}
	}
	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;
}