记录编号	550009	评测结果	AAAAAAAAAAAAAA
题目名称	[USACO Feb08] 流星雨	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.105 s
提交时间	2020-02-29 16:34:50	内存使用	14.10 MiB

#define MIN(a,b) ((a < b)? a : b)
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>

using namespace std;

struct tagBessie
{
    int x,y,step;
    tagBessie(int a = 0,int b = 0,int s = 0)
    {
        x = a,y = b,step = s;
    }
};
int farm[302][302];
bool vis[302][302];

inline bool CanGo(int x,int y,int step)
{
    if(x >= 0 && x <= 301 && y >= 0 && y <= 301)
    {
        if(step < farm[x][y] && !vis[x][y])
            return true;
    }
    return false;
}

inline void SetMeteor(int x,int y,int time)
{
    farm[x][y] = MIN(farm[x][y],time);
    if(x > 0)
        farm[x-1][y] = MIN(farm[x-1][y],time);
    if(x < 300)
        farm[x+1][y] = MIN(farm[x+1][y],time);
    if(y > 0)
        farm[x][y-1] = MIN(farm[x][y-1],time);
    if(y < 300)
        farm[x][y+1] = MIN(farm[x][y+1],time);
}

inline int BFS(int x,int y)
{
    memset(vis,false,sizeof(vis));
    queue<tagBessie> Bessie;
    Bessie.push(tagBessie());
    vis[0][0] = true;
    tagBessie B;
    while(!Bessie.empty())
    {
        B = Bessie.front();
        Bessie.pop();
        if(farm[B.x][B.y] == 0x7f7f7f7f)
            return B.step;
        if(CanGo(B.x + 1,B.y,B.step + 1))
        {
            Bessie.push(tagBessie(B.x + 1,B.y,B.step + 1));
            vis[B.x+1][B.y] = true;
        }
        if(CanGo(B.x - 1,B.y,B.step + 1))
        {
            Bessie.push(tagBessie(B.x - 1,B.y,B.step + 1));
            vis[B.x-1][B.y] = true;
        }
        if(CanGo(B.x,B.y + 1,B.step + 1))
        {
            Bessie.push(tagBessie(B.x,B.y + 1,B.step + 1));
            vis[B.x][B.y+1] = true;
        }
        if(CanGo(B.x,B.y - 1,B.step + 1))
        {
            Bessie.push(tagBessie(B.x,B.y - 1,B.step + 1));
            vis[B.x][B.y-1] = true;
        }
    }
    return -1;
}

int main()
{
    freopen("meteor.in","r",stdin);
    freopen("meteor.out","w",stdout);
    int m;
    cin >> m;
    int a,b,t;
    memset(farm,0x7f,sizeof(farm));
    for(int i = 0;i < m;i++)
    {
        cin >> a >> b >> t;
        SetMeteor(a,b,t);
    }
    cout << BFS(0,0);
    return 0;
}