【BFS】HDOJ 1072
1752 ワード
HDOJ 1072 Nightmate
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1072
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1072
#include
#include
#include
#include
using namespace std;
int maps[15][15],n,m;
int start_x,start_y;
int end_x,end_y;
struct node
{
int x;
int y;
int cnt;
int time;
};
bool check(int x,int y)
{
if(x<0 || x>=n || y<0 || y>=m || maps[x][y]==0)
return false;
return true;
}
void bfs()
{
queueq;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
node start,ends;
start.x=start_x;
start.y=start_y;
start.cnt=0;
start.time=6;
q.push(start);
while(!q.empty())
{
start=q.front();
q.pop();
int i;
if(start.x==end_x && start.y==end_y && start.time>0)
{
printf("%d
",start.cnt);
return ;
}
if(start.time==1) continue;
for(i=0;i<4;i++)
{
ends.x=start.x+dir[i][0];
ends.y=start.y+dir[i][1];
if(!check(ends.x,ends.y)) continue;
ends.cnt=start.cnt+1;
if(maps[ends.x][ends.y]==4)
{
ends.time=6;
maps[ends.x][ends.y]=1;
}
else
ends.time=start.time-1;
q.push(ends);// , ,FIFO
}
}
printf("-1
");
}
int main()
{
int i,j,t;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d %d",&n,&m);
for(i=0;i