http://acm.timus.ru/problem.aspx?space=1&num=1301
一不小心写了一个三维的spfa 思路很简单就是有点繁琐
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define LL long long
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N=15;
const int INF=0x3f3f3f3f;
//typedef pair<int,int>point;
int dist[N][N][N];
bool in[N][N][N];
int stx,sty,ndx,ndy;
struct node
{
int u[N],d[N],l[N],r[N];
}mem[N][N];
void init(int n,int m)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
mem[i][j].u[0]=4;
mem[i][j].d[0]=5;
mem[i][j].l[0]=3;
mem[i][j].r[0]=2;
mem[i][j].u[1]=5;
mem[i][j].d[1]=4;
mem[i][j].l[1]=2;
mem[i][j].r[1]=3;
mem[i][j].u[2]=2;
mem[i][j].d[2]=2;
mem[i][j].l[2]=0;
mem[i][j].r[2]=1;
mem[i][j].u[3]=3;
mem[i][j].d[3]=3;
mem[i][j].l[3]=1;
mem[i][j].r[3]=0;
mem[i][j].u[4]=1;
mem[i][j].d[4]=0;
mem[i][j].l[4]=4;
mem[i][j].r[4]=4;
mem[i][j].u[5]=0;
mem[i][j].d[5]=1;
mem[i][j].l[5]=5;
mem[i][j].r[5]=5;
}
cin>>stx>>sty;
cin>>ndx>>ndy;
char a,b,c;
while(cin>>a)
{
if(a=='v'||a=='h')
c=a;
else
{
cin>>b;
int x,y;
x=a-'0';
y=b-'0';
for(int i=0;i<6;++i)
{
if(c=='v')
{mem[x][y].d[i]=-1;mem[x+1][y].u[i]=-1;}
else
{mem[x][y].r[i]=-1;mem[x][y+1].l[i]=-1;}
}
}
}
}
void solve(int n,int m)
{
queue<int>qtx,qty,qtk;
memset(dist,-1,sizeof(dist));
dist[stx][sty][0]=0;
in[stx][sty][0]=true;
qtx.push(stx);
qty.push(sty);
qtk.push(0);
while(!qtx.empty())
{
int x=qtx.front();qtx.pop();
int y=qty.front();qty.pop();
int k=qtk.front();qtk.pop();
in[x][y][k]=false;
if(x-1>=1&&mem[x][y].u[k]!=-1)
{
int k1=mem[x][y].u[k];
if(dist[x-1][y][k1]==-1||dist[x-1][y][k1]>dist[x][y][k]+1)
{
dist[x-1][y][k1]=dist[x][y][k]+1;
if(in[x-1][y][k1]==false)
{
in[x-1][y][k1]=true;
qtx.push(x-1);qty.push(y);qtk.push(k1);
}
}
}
if(x+1<=n&&mem[x][y].d[k]!=-1)
{
int k1=mem[x][y].d[k];
if(dist[x+1][y][k1]==-1||dist[x+1][y][k1]>dist[x][y][k]+1)
{
dist[x+1][y][k1]=dist[x][y][k]+1;
if(in[x+1][y][k1]==false)
{
in[x+1][y][k1]=true;
qtx.push(x+1);qty.push(y);qtk.push(k1);
}
}
}
if(y-1>=1&&mem[x][y].l[k]!=-1)
{
int k1=mem[x][y].l[k];
if(dist[x][y-1][k1]==-1||dist[x][y-1][k1]>dist[x][y][k]+1)
{
dist[x][y-1][k1]=dist[x][y][k]+1;
if(in[x][y-1][k1]==false)
{
in[x][y-1][k1]=true;
qtx.push(x);qty.push(y-1);qtk.push(k1);
}
}
}
if(y+1<=m&&mem[x][y].r[k]!=-1)
{
int k1=mem[x][y].r[k];
if(dist[x][y+1][k1]==-1||dist[x][y+1][k1]>dist[x][y][k]+1)
{
dist[x][y+1][k1]=dist[x][y][k]+1;
if(in[x][y+1][k1]==false)
{
in[x][y+1][k1]=true;
qtx.push(x);qty.push(y+1);qtk.push(k1);
}
}
}
}
}
int main()
{
//freopen("data.in","r",stdin);
int n,m;
while(cin>>n>>m)
{
init(n,m);
solve(n,m);
if(dist[ndx][ndy][0]==-1)
cout<<"No solution"<<endl;
else
cout<<dist[ndx][ndy][0]<<endl;
}
}
