POJ 3669 简单BFS

标号 搜 完了……

//By SiriusRen
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,t,xx[]={1,-1,0,0,0},yy[]={0,0,1,-1,0},map[666][666],vis[666][555];
struct Node{int x,y,t;}node[100050],jy;
queue<Node>q;
bool check(int x,int y){
    return x>=0&&y>=0&&x<=600&&y<=600;
}
int main(){
    memset(map,-1,sizeof(map));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].t);
        for(int j=0;j<=4;j++){
            int x=node[i].x,y=node[i].y;
            if(check(x+xx[j],y+yy[j])&&(map[x+xx[j]][y+yy[j]]==-1||(node[i].t<map[x+xx[j]][y+yy[j]]&&~map[x+xx[j]][y+yy[j]]))){
                map[x+xx[j]][y+yy[j]]=node[i].t;
            }
        }
    }
    q.push(jy);
    while(!q.empty()){
        Node top=q.front();q.pop();
        for(int i=0;i<=3;i++){
            int x=top.x,y=top.y;
            if(map[x][y]==-1&&(x||y)){printf("%d
",top.t);return 0;}
            if(!vis[x+xx[i]][y+yy[i]]&&check(x+xx[i],y+yy[i])&&(top.t+1<map[x+xx[i]][y+yy[i]]||map[x+xx[i]][y+yy[i]]==-1)){
                vis[x+xx[i]][y+yy[i]]=1;
                jy.x=x+xx[i];jy.y=y+yy[i];jy.t=top.t+1;
                q.push(jy);
            }
        }
    }
    puts("-1");
}