poj3669.cpp

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <cstring>
#define N 400
#define inf 0x7f7f7f7f
using namespace std;
int n,burn[N][N],x,y,bt,nx,ny,vis[N][N];
struct Node{
    int x, y, t;
}node[50010], nd;
queue<Node>q;
int dirx[4]={0,1,0,-1};
int diry[4]={1,0,-1,0};

int bfs(int x,int y){

    nd.x = x+1; nd.y = y; nd.t = 1;
    q.push(nd);
    nd.x = x; nd.y = y+1;
    q.push(nd);
    if(burn[x][y+1]==inf||burn[x+1][y]==inf ) return 1;
    while(!q.empty()){
        nd = q.front(); q.pop();
        x = nd.x; y = nd.y;
        if(vis[x][y]) continue;
        vis[x][y]=1;
        nd.t++;
        for(int i=0;i<4;i++){
            nx = x+dirx[i]; ny = y+diry[i];
            nd.x = nx; nd.y = ny;
            if(nx<0||ny<0||nd.t>=burn[nx][ny]) continue; 
            if(burn[nx][ny]==inf && nx+ny ) return nd.t;
            q.push(nd);
        }
    }
    return -1;
}

int main(){
    scanf("%d",&n);
    memset(burn,0x7f,sizeof(burn)); //以後填入inf 都用memset 會快很多
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++) {
        scanf("%d%d%d",&x,&y,&bt);
        node[i].x = x; node[i].y = y; node[i].t = inf;
        burn[x][y]=min(burn[x][y],bt); //找出node最快被炸掉的時間
        burn[x+1][y]=min(burn[x+1][y],bt);
        burn[x][y+1]=min(burn[x][y+1],bt);
        if(x) burn[x-1][y]=min(burn[x-1][y],bt); //小心減到超出邊界
        if(y) burn[x][y-1]=min(burn[x][y-1],bt);
    }
    printf("%d\n",bfs(0,0));
}