3669.md

layout
page

#include <stdio.h>

const int MAX_TIME = 1000;
int M;
typedef struct SequenceItem {
    int x;
    int y;
} SequenceItem;
typedef struct Sequence {
    int count;
    SequenceItem items[MAX_TIME + 1];
} Sequence;

const int INF = 50000;
const int BREAK = 500001;
const int LENGTH = 301;

int maxX = 0;
int maxY = 0;
int nextMaxX, nextMaxY;
int maxTime = 0;

int tmpInt;

struct Sequence sequence[MAX_TIME + 1];

int main() {
    int position[LENGTH][LENGTH];
    int x, y, time;
    int register i, j, xi, yi;
    int answer;
    answer = INF;
    maxX = 0, maxY = 0;
    for (i = 0; i < LENGTH - 1; i++)
        for (j = 0; j < LENGTH - 1; j++)
            position[i][j] = INF;
    position[0][0] = 0;

    scanf(" %d", &M);
    for (i = 0; i < M; ++i) {
        SequenceItem item;
        scanf(" %d %d %d", &item.x, &item.y, &time);
        sequence[time].items[sequence[time].count] = item;
        sequence[time].count += 1;
        if (maxTime < time) maxTime = time;
    }

    for (i = 0; i <= maxTime; ++i) {
        for (j = 0; j < sequence[i].count; j++) {
            x = sequence[i].items[j].x;
            y = sequence[i].items[j].y;
            position[x][y] = INF;
            if (x < LENGTH - 1) position[x + 1][y] = BREAK;
            if (y < LENGTH - 1) position[x][y + 1] = BREAK;
            if (0 < x) position[x - 1][y] = BREAK;
            if (0 < y) position[x][y - 1] = BREAK;
        }

        /* move */
        nextMaxX = maxX;
        nextMaxY = maxY;
        for (xi = 0; xi <= maxX; xi++) {
            for (yi = 0; yi <= maxY; yi++) {
                if (position[xi][yi] == i) {
                    tmpInt = position[xi][yi] + 1;
                    if (xi < LENGTH - 1) {
                        if (position[xi + 1][yi] == INF) {
                            position[xi + 1][yi] = tmpInt;
                            if (xi == maxX) nextMaxX = xi + 1;
                        }
                    }
                    if (xi != 0) {
                        if (position[xi - 1][yi] == INF) {
                            position[xi - 1][yi] = tmpInt;
                        }
                    }
                    if (yi < LENGTH - 1) {
                        if (position[xi][yi + 1] == INF) {
                            position[xi][yi + 1] = tmpInt;
                            if (yi == maxY) nextMaxY = yi + 1;
                        }
                    }
                    if (yi != 0) {
                        if (position[xi][yi - 1] == INF) {
                            position[xi][yi - 1] = tmpInt;
                        }
                    }
                }
            }
        }
        maxX = nextMaxX;
        maxY = nextMaxY;
    }
    for (xi = 0; xi <= maxX; xi++) {
        for (yi = 0; yi <= maxY; yi++) {
            if (answer > position[xi][yi]) {
                answer = position[xi][yi];
            }
        }
    }

    if (answer == INF) answer = -1;

    printf("%d\n", answer);
    return 0;
}