传送门 ↬
题目描述
1944 年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 n 行,东西方向被划分为 m 列,于是整个迷宫被划分为 n×m 个单元。每一个单元的位置可用一个有序数对(单元的行号,单元的列号)来表示。南北或东西方向相邻的 2 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成 p 类,打开同一类的门的钥匙相同,不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角,即 (x,y) 单元里,并已经昏迷。迷宫只有一个入口,在西北角。也就是说,麦克可以直接进入 (1,1) 单元。另外,麦克从一个单元移动到另一个相邻单元的时间为 1,拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法,帮助麦克以最快的方式到达瑞恩所在单元,营救大兵瑞恩。
输入格式
第 1 行有 3 个整数,分别表示 n,m,p 的值。
第 2 行是 1 个整数 k,表示迷宫中门和墙的总数。
第 i+2 行 (1⩽i⩽k),有 5 个整数,依次为 xi1,yi1,xi2,yi2,gi。当 gi⩾1 时,表示 (xi1,yi1) 单元与 (xi2,yi2) 单元之间有一扇第 gi 类的门;当 gi=0 时,表示 (xi1,yi1) 单元与 (xi2,yi2) 单元之间有一堵不可逾越的墙。其中,∣xi1−xi2∣+∣yi1−yi2∣=1,0⩽gi⩽p。
第 k+3 行是一个整数 s,表示迷宫中存放的钥匙总数。
第 k+3+j 行 (1⩽j⩽s),有 3 个整数,依次为 xi1,yi1,qi 表示第 j 把钥匙存放在 (xi1,yi1)单元里,并且第 j 把钥匙是用来开启第 qi 类门的。(其中 1⩽qi⩽p)。
输入数据中同一行各相邻整数之间用一个空格分隔。
输出格式
将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解,则输出 −1。
输入输出样例
输入 #1
4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1
输出 #1
14
说明/提示
∣xi1−xi2∣+∣yi1−yi2∣=1,0⩽gi⩽p。
n,m,p⩽10,k<150,s⩽14。
分析
每走一次花费的时间都为 1,对于每次操作花费相同的问题,可以考虑用 BFS 解决。
用 map<pair<CPoint,CPoint>,int>
记录两个位置之间的墙或门,若为墙则记为 −1,表示不可逾越。用 map<CPoint,vector<int>>
记录某个位置的所有钥匙。便于查询某个位置的信息。
由于每个钥匙都可重复利用,所以同一种类的所有门只要一把钥匙就可以全部打开。不妨采用状态压缩的方式,定义整数 has,其第 k−1 位(二进制位,由低位到高位编号,最低位为第 0 位)若为 1,表示手上已经有打开第 k 类门的钥匙,其中 k⩾1。
定义状态 (x,y,has,step),表示当前位于位置 (x,y),钥匙的拥有情况为 has,且已经走了 step 步。可以用 BFS 遍历所有状态,定义函数 vis(i,j,k) 记录状态是否已经遍历过;若 vis(i,j,k) 为 1,表示位于位置 (i,j),且钥匙拥有情况为 k 的状态已经遍历过,不必再返回此状态。
搜索时,从 (x,y)走到 (x+Δx,y+Δy),需要考虑:① (x+Δx,y+Δy) 是否越界;② (x,y) 和 (x+Δx,y+Δy) 之间是否有障碍;③ 走到(x+Δx,y+Δy) 后的状态是否已经遍历到;④ 获得位于 (x+Δx,y+Δy) 的钥匙。
代码
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
|
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<queue> #include<map> #include<utility> using namespace std; const int N=12; const int inf=0x3f3f3f3f; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; struct CPoint { int r; int c; bool operator<(const CPoint& A)const { if(r==A.r) return c<A.c; else return r<A.r; } }; struct state { int x; int y; int has; int step; }; map<pair<CPoint,CPoint>,int>gap; map<CPoint,vector<int>>key; int n,m; int p; int k; int s; bool vis[N][N][N<<12]; int bfs(); int main() { cin>>n>>m>>p; cin>>k; int i; for(i=1;i<=k;i++) { int x1,y1,x2,y2,g; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g); if(!g) g=-1; gap[make_pair(CPoint{x1,y1},CPoint{x2,y2})]=g; gap[make_pair(CPoint{x2,y2},CPoint{x1,y1})]=g; } cin>>s; for(i=1;i<=s;i++) { int x,y,q; scanf("%d%d%d",&x,&y,&q); key[CPoint{x,y}].push_back(q); } if(n==1&&m==1) cout<<0<<endl; else cout<<bfs()<<endl; return 0; } int bfs() { int ans=inf; int _=0; for(auto i:key[CPoint{1,1}]) _|=(1<<i-1); vis[1][1][_]=1; queue<state>q; q.push(state{1,1,_,0}); while(!q.empty()) { state temp=q.front(); q.pop(); int x,y,has,step; for(register int i=0;i<4;i++) { x=temp.x+dx[i]; y=temp.y+dy[i]; if(x<1||x>n||y<1||y>m) continue; if(gap.count(make_pair(CPoint{temp.x,temp.y},CPoint{x,y}))) { int barrier; barrier=gap[(make_pair(CPoint{temp.x,temp.y},CPoint{x,y}))]; if(~barrier) { if(!(temp.has&(1<<barrier-1))) { continue; } } else continue; } step=temp.step+1; has=temp.has; for(auto j:key[CPoint{x,y}]) has|=(1<<j-1); if(vis[x][y][has]) continue; q.push(state{x,y,has,step}); vis[x][y][has]=1; if(x==n&&y==m) ans=min(ans,step); } } return ans==inf?-1:ans; }
|