【题意】
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，所以每个点都只会算一次。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
#define Maxn 20 int a[Maxn][Maxn][],ky[Maxn][Maxn][];
int bx[]={,,,-,},
by[]={,,,,-};
int n,m,p,sk; void init()
{
scanf("%d%d%d",&n,&m,&p);
int sm;
scanf("%d",&sm);
memset(a,,sizeof(a));
for(int i=;i<=sm;i++)
{
int x1,y1,x2,y2,g;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
if(g==) g=-;
for(int k=;k<=;k++) if(x1+bx[k]==x2&&y1+by[k]==y2)
{
a[x1][y1][k]=g;
a[x2][y2][-k]=g;
break;
}
}
scanf("%d",&sk);
memset(ky,,sizeof(ky));
for(int i=;i<=sk;i++)
{
int x,y,q;
scanf("%d%d%d",&x,&y,&q);
ky[x][y][++ky[x][y][]]=q;
}
} struct node
{
int x,y,s;
}; int dis[][][];
queue<node > q;
void spfa()
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
node ft;ft.x=;ft.y=;ft.s=;
q.push(ft);dis[][][]=;
int ans=-;
while(!q.empty())
{
node now=q.front();
int x=now.x,y=now.y,s=now.s;
for(int i=;i<=;i++) if(a[x][y][i]!=-&&x+bx[i]>=&&x+bx[i]<=n&&y+by[i]>=&&y+by[i]<=m)
{
int nx=x+bx[i],ny=y+by[i],ns=s;
if(a[x][y][i]!=&&((<<a[x][y][i]-)&s)==) continue;
// if(ky[nx][ny]) ns|=(1<<ky[nx][ny]-1);
for(int l=;l<=ky[nx][ny][];l++) ns|=(<<ky[nx][ny][l]-);
if(dis[nx][ny][ns]==-)
{
dis[nx][ny][ns]=dis[x][y][s]+;
if(nx==n&&ny==m) {ans=dis[nx][ny][ns];break;}
node tt;
tt.x=nx,tt.y=ny,tt.s=ns;
q.push(tt);
}
}
if(ans!=-) break;
q.pop();
}
printf("%d\n",ans);
} int main()
{
init();
spfa();
return ;
}
2016-11-06 14:33:08