HDU 1072 Nightmare（ 身上带有定时炸弹的他能否在炸弹爆炸之前离开—— BFS+DP思想）

 3
3 3
2 1 1
1 1 0
1 1 3
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
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 

 4
-1
13 

题目大意：

一个人在迷宫里并且身上带有定时炸弹，炸弹经过6秒就会爆炸，在这个迷宫里面有5种属性的方格，2代表出发点，3代表出口，1代表可以走的路，0代表墙，4代表在此点可以把当前的定时炸弹重置为6 . PS：在出口可以出去的条件是定时炸弹剩余时间大于0，同样重置炸弹时间的条件是当前炸弹的爆炸时间大于0.

解题思路：

BFS+DP，当遇到下一步可以带的时间比实际那一步多则更新爆炸时间。.

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

int dirI[4]={1,0,-1,0},is,js,ie,je,n,m;
int dirJ[4]={0,1,0,-1},timen[10][10];

struct node{
    int i,j,t,v;
    node(int i0=0,int j0=0,int t0=0,int v0=0){
        i=i0,j=j0,t=t0,v=v0;
    }
}a[10][10];

void bfs(){
    queue <node> path;
    timen[is][js]=0;
    a[is][js].t=6;
    bool ans=false;
    path.push(a[is][js]);
    while(!path.empty()&&!ans){
        node s=path.front();
        path.pop();
        for(int i=0;i<4;i++){
            int di=s.i+dirI[i],dj=s.j+dirJ[i];
            if(a[di][dj].v==0||di<0||dj<0||di>=n||dj>=m) continue;
            int temp=timen[s.i][s.j]+1,st=s.t-1 ;
            if(st>a[di][dj].t||timen[di][dj]==-1){
                if(a[di][dj].v==4&&st>=1) {st=6;a[di][dj].t=st;timen[di][dj]=temp;path.push(a[di][dj]);}
                if(a[di][dj].v==1) {a[di][dj].t=st;timen[di][dj]=temp;path.push(a[di][dj]);}
                if(a[di][dj].v==3&&st>=1){ans=true;timen[di][dj]=temp;break;}
            }
        }
    }
    printf("%d\n",timen[ie][je]);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(timen,-1,sizeof(timen));
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf("%d",&a[i][j].v);
                a[i][j].i=i,a[i][j].j=j,a[i][j].t=0;
                if(a[i][j].v==2) {is=i,js=j;}
                if(a[i][j].v==3) {ie=i,je=j;}
            }
        }
        bfs();
    }
    return 0;
}