题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1072
从入口到出口的最短路，4这个点要重置时间，不运行重复走，其他个点可以重复走，其中0是障碍，先前自己用深度优先不好搞，再借鉴了网上一个大牛的
转自：http://blog.csdn.net/yyf573462811/article/details/7819226
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
int maze[20][20];
struct node
{
int x,y,step,count;
}p,q;
int n,m,sx,sy;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void bfs()
{
queue<node> Q;
p.x=sx;
p.y=sy;
p.step=0;
p.count=6;
maze[sx][sy]=0;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
for(int i=0;i<4;i++)
{
q=p;
q.x+=dir[i][0];
q.y+=dir[i][1];
if(q.x<=0||q.x>n||q.y<=0||q.y>m||maze[q.x][q.y]==0)continue;
if(maze[q.x][q.y]==1){
q.count--;
if(q.count>=1){
q.step++;
Q.push(q);
}
// maze[q.x][q.y]=0; 如果不允许重复，则最后一个数据无法到达
}
else if(maze[q.x][q.y]==4){
q.count--;
if(q.count>=1){
q.step++;
q.count=6;
Q.push(q);
}
maze[q.x][q.y]=0; //只有4这点不能重复走，其他可重复走
}
else if(maze[q.x][q.y]==3&&q.count>1){
q.step++;
cout<<q.step<<endl;
return ;
}
}
}
cout<<-1<<endl;
}
int main()
{
int t;
// ifstream fin;
// fin.open("data1.txt");
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>maze[i][j];
if(maze[i][j]==2){
sx=i;
sy=j;
}
}
}
bfs();
}
return 0;
}