广搜最短路(最短时间到达目的地)，POJ(3669)

题目链接：http://poj.org/problem?id=3669

解题报告：

1、流星坠落的点，四周和自己本身都被毁灭，不断更新每个点被毁灭的时候的最短时间。

2、搜索终点是，到达某个点，这个不会有流星毁灭他，即他的毁灭的时间大于最后一个流星到达时的时间。

 

#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;

#define MAX 302        ///地图宽度

int m;    ///流星数
int map[MAX][MAX];    ///地图
bool visited[MAX][MAX];    ///是否访问过
int last;    ///最晚的流星时间

int go[][2] ={{1,0},{-1,0},{0,1},{0,-1},{0,0}}; ///五个方向


struct Meteor
{
    int x;
    int y;
    int t;
}meteor[50000];    ///流星结构

typedef Meteor Node;    ///节点结构，用于bfs

int max(int a, int b)
{
    return a > b ? a : b;
}

int bfs()
{
    memset(visited, false, sizeof(visited));

    queue<Node> q;    ///队列

    Node fir;    ///起始点入队
    fir.x = fir.y = fir.t = 0;
    visited[0][0] = true;

    q.push(fir);

    while (!q.empty())    ///bfs
    {
        Node now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)    ///每次必须行动1格
        {
            Node tmp = now;
            tmp.x += go[i][0];
            tmp.y += go[i][1];
            tmp.t++;

            if (tmp.x >= 0 && tmp.y >= 0 && map[tmp.x][tmp.y]>tmp.t && !visited[tmp.x][tmp.y])    ///没越界、流星还未砸这个格子、还没访问过(重复访问就是不是bfs最优解了)
            {
                visited[tmp.x][tmp.y] = true;    ///标记
                if (map[tmp.x][tmp.y] > last)    ///如果格子不会被砸到
                {
                    return tmp.t;
                }
                q.push(tmp);
            }
        }
    }
    return -1;
}

int main()
{
    while (scanf("%d", &m) != EOF)
    {
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &meteor[i].x, &meteor[i].y, &meteor[i].t);
        }

        memset(map, 0x7f, sizeof(map));    ///要严谨一点可以用0x7fffffff，不过就不能用memset了
        for (int i = 0; i < m; i++)
        {
            ///计算最晚流星的时间
            if (i == 0)
                last = meteor[i].t;
            else
                last = max(last, meteor[i].t);

            ///更新地图上某个点的最快的流星下落时间
            for (int j = 0; j < 5; j++)
            {
                int tx = meteor[i].x + go[j][0];
                int ty = meteor[i].y + go[j][1];

                if (tx >= 0 && ty >= 0 && map[tx][ty]>meteor[i].t)
                {
                    map[tx][ty] = meteor[i].t;
                }
            }
        }

        if (map[0][0] == 0)    ///起始点被砸直接gg
            printf("-1\n");
        else  ///否则bfs
            printf("%d\n", bfs());
    }
    return 0;
}