POJ 3669

#include <iostream>
#include <queue>
using namespace std;
#define T_ori 1005

struct pos
{
    int x;//可行x坐标
    int y;//可行y坐标
    int t;//该点最小时间
};

queue<pos> que_pos,que_pos2;//前者是待扩张位置队列,后者用来存储稳定位置队列

int T_used[305][305];//节点时间使用情况
short used[305][305];//访问记录

void bfs(int t_now, int times) //当前时间为t_now,需进行times次的bfs
{
    if(times <= 0)
    {
        return;
    }
    int s = que_pos.size();//可行点的个数
    for (int i = 0; i < s;i++)
    {
        pos fro = que_pos.front();
        //该点未访问过则处理
        if(used[fro.x][fro.y] == 0)
        {
            //访问记录更新
            used[fro.x][fro.y] = 1;
            //如果该点当下时间安全
            if(t_now < T_used[fro.x][fro.y])
            {
                //该点插入稳定点队列
                que_pos2.push(fro);
                //尝试左移
                if((fro.x > 0)&&(used[fro.x - 1][fro.y] == 0)) 
                {
                    pos tmp = {fro.x - 1, fro.y, fro.t + 1};
                    que_pos.push(tmp);
                }
                //尝试右移
                if((fro.x < 304)&&(used[fro.x + 1][fro.y] == 0))
                {
                    pos tmp = {fro.x + 1, fro.y, fro.t + 1};
                    que_pos.push(tmp);
                }
                //尝试上移
                if(((fro.y < 304)&&used[fro.x][fro.y + 1] == 0))
                {
                    pos tmp = {fro.x, fro.y + 1, fro.t + 1};
                    que_pos.push(tmp);
                }
                //尝试下移
                if((fro.y > 0)&&(used[fro.x][fro.y - 1] == 0)) 
                {
                    pos tmp = {fro.x, fro.y - 1, fro.t + 1};
                    que_pos.push(tmp);
                }
            }
        }
        que_pos.pop();//队伍头删除
    }
    bfs(t_now + 1, times - 1);//当前时间更新+1，需进行times次的bfs
}

int last()//最后一次判断安全并计算最小时间
{
    int s = que_pos.size();//可行点的个数
    int min_time = 1005;
    for (int i = 0; i < s;i++)
    {
        pos fro = que_pos.front();
        //该点未被破坏则计算最小时间
        if(T_used[fro.x][fro.y] == T_ori)
        {
            min_time = min(min_time, fro.t);
        }
        que_pos.pop();
    }
    s = que_pos2.size();//稳定点的个数
    for (int i = 0; i < s;i++)
    {
        pos fro = que_pos2.front();
        //该点未被破坏则计算最小时间
        if(T_used[fro.x][fro.y] == T_ori)
        {
            min_time = min(min_time, fro.t);
        }
        que_pos2.pop();
    }
    return min_time;
}

int main()
{
    int M; //流星个数
    cin >> M;//流星个数输入
        
    for (int i = 0; i < 305;i++)
    {
        for (int j = 0; j < 305;j++)
        {
            T_used[i][j] = T_ori; //流星轰炸时间初始化
            used[i][j] = 0;       //节点访问状态初始化
        }
    }
    int x, y, t;//流星坐标与时间
    int max_t = 0;//最大可能移动时间
    for (int i = 0;i < M;i++)
    {
        cin >> x >> y >> t;//流星坐标与时间
        //流星到达中心摧毁
        T_used[x][y] = min(t, T_used[x][y]);
        //左边摧毁
        if(x > 0) T_used[x - 1][y] = min(t, T_used[x - 1][y]);
        //右边摧毁
        if(x < 304) T_used[x + 1][y] = min(t, T_used[x + 1][y]);
        //上边摧毁
        if(y < 304) T_used[x][y + 1] = min(t, T_used[x][y + 1]);
        //下边摧毁
        if(y > 0) T_used[x][y - 1] = min(t, T_used[x][y - 1]);
        max_t = max(max_t, t);//更新最大可能移动时间
    }
    
    pos pos_tmp = {0, 0, 0};//初始坐标
    que_pos.push(pos_tmp);
    bfs(0, max_t);//广度搜索
    int time = last();
    if(time <= 1000)
    {
        cout << time << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}