Description
这是一个传说中的勇者凡喵，救出被掳走的公主，顺道打倒妄图控制世界的恶龙拯救世界的故事。
有趣的是，凡喵这一次进入恶龙巢穴时，发现恶龙刚好外出。于是凡喵决定先去拯救公主，至于拯救世界什么 的，还是开心最重要。
凡喵出发前从冒险者公会购买了一张恶龙巢穴的地图。
恶龙巢穴建立在地下。一共有 H 层，从地下 1 层到地下 H 层。每层是一个迷宫，有 N × M 个格子。
用 (x, y, i) 表示第 i 层第 x 行第 y 列的格子，凡喵已经知道入口的位置是 (SX, SY, 1) 而公主被囚禁在 (T X, T Y, H)。
格子有 3 种类型，分别是陷阱，传送门和空地。凡喵每 1 分钟可以从一个格子走到相邻的格子（相邻的定义 是在同一层且有一条公共边）。当然，凡喵是不能走到陷阱上的。
传送门一共有 10 种，第 i 层的传送门可以将凡喵传送到第 i + 1 层任意一个同类型的传送门处。传送是不需 要时间的。当传送到一个传送门时，可以立刻再从这个传送门出发传送到下一层。
现在凡喵想要知道，自己最少要多少分钟才能见到公主。
Data Constraint
Solution
我们可以每次将有颜色的点加入spfa的起始队列，跑完spfa后我们选出每种颜色在该层的与起点最近距离，作为答案更新下一层的同种颜色的起始距离。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=
2e2+
5;
const int f[
4][
2]={{
0,
1},{
1,
0},{
0,-
1},{-
1,
0}};
struct code{
int x,y;
}v[maxn*maxn*
10];
int a[
11][maxn][maxn],d[
11][maxn][maxn],b[
20],bz[maxn][maxn];
int sx,sy,tx,ty,n,m,h,i,t,j,k,l,x,y,z,p,num;
void spfa(
int s){
int i=
0,j=num,x,k,t;
while (i<j){
++i;z=d[s][v[i].x][v[i].y];
for (k=
0;k<
4;k++){
x=v[i].x+f[k][
0];y=v[i].y+f[k][
1];
if (x>n || x<
1 || y>m || y<
1 || d[s][x][y]<=z+
1 || a[s][x][y]<
0)
continue;
d[s][x][y]=z+
1;
if (!bz[x][y]) v[++j].x=x,v[j].y=y,bz[x][y]=
1;
}
bz[v[i].x][v[i].y]=
0;
}
}
int main(){
freopen(
"rpg.in",
"r",stdin);freopen(
"rpg.out",
"w",stdout);
scanf(
"%d%d%d",&n,&m,&h);
for (i=
1;i<=h;i++)
for (j=
1;j<=n;j++)
for (k=
1;k<=m;k++)
scanf(
"%d",&a[i][j][k]);
scanf(
"%d%d%d%d",&sx,&sy,&tx,&ty);
if (a[
1][sx][sy]<
0 || a[h][tx][ty]<
0){
printf(
"-1\n");
return 0;
}
memset(d,
127,
sizeof(d));p=d[
1][
1][
1];
d[
1][sx][sy]=
0;
for (i=
1;i<=h;i++){
num=
0;
for (j=
1;j<=n;j++)
for (k=
1;k<=m;k++)
if (d[i][j][k]!=p)v[++num].x=j,v[num].y=k,bz[j][k]=
1;
spfa(i);
memset(b,
127,
sizeof(b));
for (j=
1;j<=n;j++)
for (k=
1;k<=m;k++)
b[a[i][j][k]]=min(b[a[i][j][k]],d[i][j][k]);
for (j=
1;j<=n;j++)
for (k=
1;k<=m;k++)
if (a[i+
1][j][k]>
0) d[i+
1][j][k]=b[a[i+
1][j][k]];
}
if (d[h][tx][ty]!=p)
printf(
"%d\n",d[h][tx][ty]);
else printf(
"-1\n");
}
