题目地址:http://poj.org/problem?id=3669

题目大意

大意是这样的,在一片区域中流星下坠,在$T$时刻下坠到$(x, y)$点,$0 \le x \le 300, 0 \le y \le 300$,并且该点相邻四个格子也遭受到破坏。

一个人起始在$(0, 0)$位置,以每秒1格的速度,逃离到安全区域,求最小逃离时间,若不能到达,则输出-1。

思路

这题思路主要是先构造出损坏的格子的地图,然后在地图上宽度优先搜索。

若搜索到未损坏的格子,则搜索到该格子的时间为到达安全区域最小值。

若搜索到已损坏的格子,且到达该格子的时间小于损坏的时间,则入队。

坑也不少,时间更新问题,还有区域问题。流星下落最大坐标是300,由于相邻格子也受影响,那么可破坏到301,人也可以逃到302格。

AC代码

/*************************************************************************
    > File Name: 3669.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-08-29 六 19:10:35 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
int M;
struct meteor {
    int x, y, t;
    meteor(int x=0, int y=0,int t=0) : x(x), y(y), t(t) {}
};

bool visited[310][310]; // 标记已访问点
int T[310][310];  // 标记流星掉落时间点

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

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

    int time = -1; // 初始不可达
    visited[0][0] = true; // 标记起点
    queue<meteor> que;
    que.push(meteor(0, 0, 0));

    while(!que.empty()) {
        meteor p = que.front(); que.pop();
         if(T[p.x][p.y] == INF) { // 这块是安全的
            time = p.t;
            break;
        }
         else if(T[p.x][p.y] !=INF && p.t < T[p.x][p.y]) {
            for(int k=0; k<4; ++k) {
                meteor q(p.x+dx[k], p.y+dy[k], p.t + 1);
                if(!visited[q.x][q.y] && q.x >=0 && q.x <= 302 && q.y >=0 && q.y <= 302) {
                    que.push(q);
                    visited[q.x][q.y] = true;
                }
            }
        }
    }
    return time;
}

void solve() {
    scanf("%d", &M);
    int x, y, t;
    memset(T, 0x3f, sizeof(T));

    for (int i = 0; i < M; ++i) {
        scanf("%d%d%d", &x, &y, &t);
        if(T[x][y] > t) // 这里有坑。。。时间更新问题,好大的坑。。
            T[x][y] = t;
        for(int k=0; k<4; ++k) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if(nx >=0 && nx<=301 && ny >= 0 && ny <= 301 && T[nx][ny] > t)
                T[nx][ny] = t;
        }

    }

    // for(int i=0; i<=10; ++i) {
        // for(int j=0; j<=10; ++j) {
            // if(T[i][j] == INF) printf("-1 ");
            // else printf("%3d", T[i][j]);
        // }
        // puts("");
    // }

    cout << bfs() << endl;
}

int main()
{
#ifdef Oj
    freopen("3669.in", "r", stdin);
#endif
    solve();
    return 0;
}