题目链接

Meteor Shower POJ - 3669

思路

题意很简单。一个小技巧是彗星落在地上除本身所在的位置外，其他上下左右四块地方可以在一开始预处理。再一个就是两个英文短语 the origin（原点）这表明出发点在(0, 0)，first quadrant（第一象限）这表明地图不止到300，我一开始判断300WA了好久。

英语一定要学好，万一签个什么合同英文的被坑了呢？

时间复杂度

$$ O(N^2) $$

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 310;
const int INF = 0x3f3f3f3f;

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

bool check(int x, int y) {
    if (0 <= x && x <= 301 && 0 <= y && y <= 301) {
        return true;
    } else {
        return false;
    }
}

int bfs() {
    if (a[0][0] == 0){
        return -1;
    }
    queue<pair<int, int> > que;
    que.push(make_pair(0, 0));
    vis[0][0] = 0;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        int x = cur.first;
        int y = cur.second;
        int t = vis[x][y] + 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (check(xx, yy) && vis[xx][yy] == -1) {
                if (a[xx][yy] == INF) {
                    return t;
                }
                if (a[xx][yy] > t) {
                    vis[xx][yy] = t;
                    que.push(make_pair(xx, yy));
                }
            }
        }
    }

    return -1;
}

int main() {
    memset(a, 0x3f, sizeof a);
    memset(vis, -1, sizeof vis);
    int k;
    scanf("%d", &k);// don't forget &
    for (int i = 1; i <= k; i++) {
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t);// don't forget &
        a[x][y] = min(a[x][y], t);
        for (int j = 0; j < 4; j++) {
            int xx = x + dx[j];
            int yy = y + dy[j];
            if (check(xx, yy)) {
                a[xx][yy] = min(a[xx][yy], t);
            }
        }
    }
    printf("%d", bfs());
    return 0;
}