首页 > 代码库 > 【网络流24题】 No.14 孤岛营救问题 （分层图最短路）

【网络流24题】 No.14 孤岛营救问题 （分层图最短路）

2024-08-19 07:35:38   219人阅读

【题意】

　　1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛， 营救被
敌军俘虏的大兵瑞恩。 瑞恩被关押在一个迷宫里， 迷宫地形复杂， 但幸好麦克得到了迷宫的
地形图。 迷宫的外形是一个长方形， 其南北方向被划分为 N 行，东西方向被划分为 M 列，
于是整个迷宫被划分为 N× M 个单元。每一个单元的位置可用一个有序数对(单元的行号，
单元的列号)来表示。南北或东西方向相邻的 2 个单元之间可能互通， 也可能有一扇锁着的
门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙， 并且所有的门被分成 P 类，
打开同一类的门的钥匙相同， 不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即(N， M)单元里， 并已经昏迷。 迷宫只有一个入口，
在西北角。 也就是说， 麦克可以直接进入(1， 1)单元。 另外，麦克从一个单元移动到另一个
相邻单元的时间为 1， 拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

′数据输入：
由文件 input.txt 提供输入数据。 第 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）。
输入数据中同一行各相邻整数之间用一个空格分隔。

 

输入文件示例
input.txt
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

输出文件示例
output.txt
14

 

 

 

【分析】

　　就是分层图最短路，钥匙状压加入状态点中。

　　然后路径长度都是-1，所以每个点都只会算一次。

技术分享

 

技术分享 
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 #define Maxn 20
11 
12 int a[Maxn][Maxn][6],ky[Maxn][Maxn][20];
13 int bx[6]={0,0,1,-1,0},
14     by[6]={0,1,0,0,-1};
15 int n,m,p,sk;
16 
17 void init()
18 {
19     scanf("%d%d%d",&n,&m,&p);
20     int sm;
21     scanf("%d",&sm);
22     memset(a,0,sizeof(a));
23     for(int i=1;i<=sm;i++)
24     {
25         int x1,y1,x2,y2,g;
26         scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
27         if(g==0) g=-1;
28         for(int k=1;k<=4;k++) if(x1+bx[k]==x2&&y1+by[k]==y2)
29         {
30             a[x1][y1][k]=g;
31             a[x2][y2][5-k]=g;
32             break;
33         }
34     }
35     scanf("%d",&sk);
36     memset(ky,0,sizeof(ky));
37     for(int i=1;i<=sk;i++)
38     {
39         int x,y,q;
40         scanf("%d%d%d",&x,&y,&q);
41         ky[x][y][++ky[x][y][0]]=q;
42     }
43 }
44 
45 struct node
46 {
47     int x,y,s;
48 };
49 
50 int dis[20][20][1010];
51 queue<node > q;
52 void spfa()
53 {
54     while(!q.empty()) q.pop();
55     memset(dis,-1,sizeof(dis));
56     node ft;ft.x=1;ft.y=1;ft.s=0;
57     q.push(ft);dis[1][1][0]=0;
58     int ans=-1;
59     while(!q.empty())
60     {
61         node now=q.front();
62         int x=now.x,y=now.y,s=now.s;
63         for(int i=1;i<=4;i++) if(a[x][y][i]!=-1&&x+bx[i]>=1&&x+bx[i]<=n&&y+by[i]>=1&&y+by[i]<=m)
64         {
65             int nx=x+bx[i],ny=y+by[i],ns=s;
66             if(a[x][y][i]!=0&&((1<<a[x][y][i]-1)&s)==0) continue;
67             // if(ky[nx][ny]) ns|=(1<<ky[nx][ny]-1);
68             for(int l=1;l<=ky[nx][ny][0];l++) ns|=(1<<ky[nx][ny][l]-1);
69             if(dis[nx][ny][ns]==-1)
70             {
71                 dis[nx][ny][ns]=dis[x][y][s]+1;
72                 if(nx==n&&ny==m) {ans=dis[nx][ny][ns];break;}
73                 node tt;
74                 tt.x=nx,tt.y=ny,tt.s=ns;
75                 q.push(tt);
76             }
77         }
78         if(ans!=-1) break;
79         q.pop();
80     }
81     printf("%d\n",ans);
82 }
83 
84 int main()
85 {
86     init();
87     spfa();
88     return 0;
89 }
View Code

 

技术分享

 

2016-11-06 14:33:08

【网络流24题】 No.14 孤岛营救问题 （分层图最短路）


联系
我们