POJ 3669 Meteor Shower

Description

巨大流星雨即将袭来。每个流星会对击中的地方以及周围（上下左右四格）造成破坏。Bessie开始时位于（0, 0）位置，并希望逃到一处不会被袭击到的地方（在第一象限内）。已知每移动一格需要1个时间单位，被流星破坏后的地方不能再进入。给出M个流星在T时刻击中的地方（X, Y），问Bessie能否逃到安全的地方，若能输出最短时间，否则输出-1。

http://poj.org/problem?id=3669

Idea

简单搜索，需要注意的是：若某处被反复袭击，时间点取最早的那一刻

所以说：Think twice, code once. 可平时没这样的习惯到场上应该也不会有（平时会觉得耽误时间……加之动脑少，思考的少，但凡有点细节便会忽视……要改！）

另外发现，map映射会比数组要慢，如果不是不知空间的情况下，尽量不用map

Code

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

int n;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool vis[305][305];
//map<int, map<int, int> >ruin;
//map<int, map<int, bool> >is;
int ruin[305][305];
bool is[305][305];

struct node
{
    int x, y, step;
};

void BFS()
{
    node now, nxt;
    now.x = 0, now.y = 0, now.step = 0;
    vis[0][0] = 1;
    queue<node> q;
    q.push(now);
    bool flag = 0;
    while(q.size())
    {
        now = q.front();
        q.pop();

        if(is[now.x][now.y] == 0)
        {
            flag = 1;
            cout << now.step << '\n';
            return ;
        }

        for(int i = 0; i < 4; ++i)
        {
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            if(xx < 0 || yy < 0 || vis[xx][yy])
                continue;
            if(is[xx][yy] == 1 && ruin[xx][yy] <= now.step + 1)
                continue;
            vis[xx][yy] = 1;
            nxt.x = xx, nxt.y = yy, nxt.step = now.step + 1;
            q.push(nxt);
        }
    }
    if(flag == 0)
        cout << "-1" << '\n';
    return ;
}

int main()
{
    scanf("%d", &n);
    int x, y, t;
    for(int i = 0; i < n; ++i)
    {
        scanf("%d%d%d", &x, &y, &t);
        if(is[x][y] == 0)
            ruin[x][y] = t, is[x][y] = 1;
        else
            ruin[x][y] = min(ruin[x][y], t);

        for(int i = 0; i < 4; ++i)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx < 0 || yy < 0)
                continue;
            if(is[xx][yy] == 0)
                ruin[xx][yy] = t, is[xx][yy] = 1;
            else
                ruin[xx][yy] = min(ruin[xx][yy], t);
        }
    }
    BFS();
    return 0;
}

用二维mapTLE了半小时