学步园

hdu1072 nightmare

……跟hdu1242有些不同

走过的路可以返回

所以不要标记，换炸弹的倒计时限制队列的增长

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;

int mp[10][10],m,n,Sx,Sy,Dx,Dy,flag,dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
struct point
{
	int x,y,time,step;
};

void bfs(int x,int y)
{
	int i;
	point t,tt;
	queue<point>Q;
	t.x=x;t.y=y;t.step=0;t.time=6;
	Q.push(t);
//	memset(visit,0,sizeof(visit));
	while(!Q.empty())
	{
		t=Q.front();
		Q.pop();//printf("%d,%d\n",t.x,t.y);
		for(i=0;i<4;i++)
		{
 			tt.x=t.x+dir[i][0];tt.y=t.y+dir[i][1];  tt.step=t.step+1;tt.time=t.time-1;
 		//	printf("\t%d,%d",tt.x,tt.y);
			if(tt.x<1||tt.x>m||tt.y<1||tt.y>n||mp[tt.x][tt.y]==0||tt.time==0)	continue;
			if(mp[tt.x][tt.y]==3){printf("%d\n",tt.step);return;}
			
		//	printf("!\n");
			
			if(mp[tt.x][tt.y]==4){
				mp[tt.x][tt.y]=0;
				tt.time=6;
			//	memset(visit,0,sizeof(visit));
			}
		//	mp[tt.x][tt.y]=0;
			Q.push(tt);
 		}
 	//	system("pause");
	}
	printf("-1\n");
	return;
}

int main()
{
	int T,i,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&m,&n);
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				scanf("%d",&mp[i][j]);
				if(mp[i][j]==2) Sx=i,Sy=j;
			}
		}
		
		bfs(Sx,Sy);
		
	}
	return 0;
}