# hdu 5094 Maze bfs

```/******************************************************
* File Name:   5094.cpp
* Author:      kojimai
* Create Time: 2014年11月03日 星期一 09时24分27秒
******************************************************/

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define FFF 55
bool vis[FFF][FFF][2048];
int move[4][2] ={-1,0,0,1,1,0,0,-1};//0-up 1-right 2-down 3-left
struct node
{
int x,y,t,key;
}now,tmp;
queue<node> pp;

int getg(int g)
{
if(g == 0)
return -1;
else
return 1 << g;
}
void solve(int x1,int y1,int x2,int y2,int g)
{
if(x1 == x2)
{
if(y1<y2)
{
}
else
{
}
}
else if(x1 < x2)
{
}
else
{
}
return;
}
bool judge(int dir)
{
return false;
return true;
return false;
else
return true;
}
void printr()
{
for(int k = 0;k <= 3;k++)
{
cout<<" "<<k<<endl;
for(int i = 1;i <= 4;i++)
{
for(int j = 1;j <= 4;j++)
{
}
cout<<endl;
}
}
}
void printm()
{
for(int i = 1;i <=  4;i++)
{
for(int j = 1;j <= 4;j++)
{
cout<<map[i][j]<<' ';
}
cout<<endl;
}
}

int main()
{
int n,m,p,s,x1,x2,y1,y2,g,k,key;
while(~scanf("%d",&n))
{
while(!pp.empty()) pp.pop();
scanf("%d%d",&m,&p);
scanf("%d",&k);
memset(map,0,sizeof(map));
while(k--)
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
solve(x1,y1,x2,y2,g);
}
scanf("%d",&s);
while(s--)
{
scanf("%d%d%d",&x1,&y1,&key);
map[x1][y1] |= (1<<key);
}
memset(vis,false,sizeof(vis));
int ans = -1;
now.x = 1;now.y = 1;now.key = map[1][1];now.t = 0;
vis[1][1][now.key] = true;
pp.push(now);
//printr();
//printm();
while(!pp.empty())
{
now = pp.front();pp.pop();
//cout<<" x = "<<now.x<<" y = "<<now.y<<" t = "<<now.t<<" key = "<<now.key<<endl;
if(now.x == n&&now.y == m)
{
ans = now.t;
break;
}
tmp.t = now.t + 1;
int xx,yy;
for(int i = 0;i < 4;i++)
{
if(judge(i))
{
xx = now.x + move[i][0];
yy = now.y + move[i][1];
if(xx <= 0 || xx > n || yy <= 0 || yy > m)
continue;
else
{
tmp.key = now.key | map[xx][yy];
tmp.x = xx;
tmp.y = yy;
if(!vis[tmp.x][tmp.y][tmp.key])
{
vis[tmp.x][tmp.y][tmp.key] = true;
pp.push(tmp);
}
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
```

每一个你不满意的现在，都有一个你没有努力的曾经。
一个历史类的公众号，欢迎关注