HDU-1072:Nightmare(BFS)

BFS

题面链接

• 题意

  走迷宫。一个爆炸时间为6分钟的炸弹，每往相邻的地方走一步，就消耗一分钟，到达某些特殊点可以重置炸弹爆炸时间为6分钟，到达任一点时的时间不能为0，可以走重复路，如果能够走出迷宫，求出最短时间。如果不能走出则输出-1.

  0：该地区是一个墙,不能上墙。
  1：该区域能够走的路。
  2：起始位置。
  3：迷宫的出口，目标位置。
  4：该区域包含一个炸弹重置设备，可以步行到这些地区延迟爆炸的时间。

• 样例

  Sample Input
  3 ///有3组测试数据
  3 3 ///3*3的矩阵
  2 1 1
  1 1 0
  1 1 3
  4 8 ///4*8的矩阵
  2 1 1 0 1 1 1 0
  1 0 4 1 1 0 4 1
  1 0 0 0 0 0 0 1
  1 1 1 4 1 1 1 3
  5 8 ///5*8的矩阵
  1 2 1 1 1 1 1 4
  1 0 0 0 1 0 0 1
  1 4 1 0 1 1 0 1
  1 0 0 0 0 3 0 1
  1 1 4 1 1 1 1 1

  Sample Output
  4
  -1
  13

• 代码

#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int vis[111][111];///vis[x][y]为起点到坐标为（x，y）的点的最短距离
int i,j,x,y,t,n,m;
int a[111][111];///输入的矩阵
struct node
{
   int x,y,step,time;
};
int BFS()
{
    node now,next;
    queue<node>q;
    now.x=x;
    now.y=y;
    now.step=0;
    now.time=6;
    q.push(now);
    vis[now.x][now.y]=6;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x>=0&&next.x<m&&next.y>=0&&next.y<n&&a[next.x][next.y]!=0)
                {
                    next.step=now.step+1;
                    next.time=now.time-1;
                    if(next.time<=0)
                        continue;
                    if(a[next.x][next.y]==4)
                    {
                        a[next.x][next.y]=0;
                        next.time=6;
                    }
                    if(a[next.x][next.y]==3)
                    {
                        if(next.time>0)
                        {
                             t=next.step;
                             return t;
                        }
                    }
                    if(next.time>=1&&vis[next.x][next.y]<next.time)
                    {
                        vis[next.x][next.y]=next.time;
                        q.push(next);
                    }
              }
        }
    }
     return -1;
}
int main()
{
    int k,count;
    scanf("%d",&k);
    while(k--)
    {
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));
        scanf("%d%d",&m,&n);
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
        }
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
            {
                if(a[i][j]==2)
                {
                   x=i;
                   y=j;
                }
            }
        count=BFS();
        printf("%d\n",count);
    }
    return 0;
}