poj3669Meteor Shower(bfs)

題目請戳這裡

題目大意:在二維平面上,有個人一開始在原點,現在有一場流星雨,已知有n個,第i個流星第ti秒落在(xi,yi)位置,并且(xi,yi)周圍4個位置也會遭殃.人每秒走機關長度,并且隻能向四個方向走,并且走的位置要在流行毀滅這一點之前.求這個人最快脫險時間.無法脫險輸出-1.

題目分析:簡單搜尋,bfs妥妥的

.首先用flag數組記錄下所有位置最先遭殃的時間.然後從源點開始bfs.直到找到一個安全的地點為止.

trick:題目描述有誤,二維平面範圍不止300!要大一點!!

詳情請見代碼:

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 402;
const int M = 50005;
const int NM = 50004;
const int inf = 0x3f3f3f3f;
struct node
{
    int x,y,t;
    bool operator< (const node a)const
    {
        return t < a.t;
    }
}pt[M],que[NM],ss,now;
int flag[N][N];
bool vis[N][N];
int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
int n;

bool isok(int x,int y)
{
    return (x >= 0 && y >= 0 && x <= 400 && y <= 400);
}

int bfs()
{
    ss.x = ss.y = ss.t = 0;
    int i,head,tail;
    head = tail = 0;
    que[tail ++] = ss;
    vis[0][0] = true;

    while(head != tail)
    {
        now = que[head ++];
        if(head == NM)
            head = 0;
        if(flag[now.x][now.y] == inf)
            return now.t;
        ss = now;
        ss.t ++;
        for(i = 0;i < 4;i ++)
        {
            ss.x = now.x + dir[i][0];
            ss.y = now.y + dir[i][1];
            if(vis[ss.x][ss.y] || !isok(ss.x,ss.y))
                continue;
            if(flag[ss.x][ss.y] == inf)
                return ss.t;
            if(ss.t < flag[ss.x][ss.y])
            {
                vis[ss.x][ss.y] = true;
                que[tail ++] = ss;
                if(tail == NM)
                    tail = 0;
            }
        }
    }
    return -1;
}

int main()
{
    int i,j;
    while(scanf("%d",&n) != EOF)
    {
        memset(flag,0x3f,sizeof(flag));
        memset(vis,false,sizeof(vis));
        for(i = 0;i < n;i ++)
        {
            scanf("%d%d%d",&pt[i].x,&pt[i].y,&pt[i].t);
            flag[pt[i].x][pt[i].y] = min(flag[pt[i].x][pt[i].y],pt[i].t);
            for(j = 0;j < 4;j ++)
            {
                if(isok(pt[i].x + dir[j][0],pt[i].y + dir[j][1]))
                    flag[pt[i].x + dir[j][0]][pt[i].y + dir[j][1]] = min(pt[i].t,flag[pt[i].x + dir[j][0]][pt[i].y + dir[j][1]]);
            }
        }
        printf("%d\n",bfs());
    }
    return 0;
}