391 lines
12 KiB
C
391 lines
12 KiB
C
|
#include <stdio.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <string.h>
|
||
|
|
|
||
|
|
#define BUFFER_SIZE 256
|
||
|
|
#define MAX_MAP_SIZE 1024
|
||
|
|
#define MAX_BLIZZARDS 4096
|
||
|
|
#define MAX_BLIZZARDS_HISTORY 4096
|
||
|
|
#define FIFO_MAX 32*1024*1024
|
||
|
|
|
||
|
|
enum direction {
|
||
|
|
RIGHT,
|
||
|
|
DOWN,
|
||
|
|
LEFT,
|
||
|
|
UP
|
||
|
|
};
|
||
|
|
|
||
|
|
typedef struct blizzard {
|
||
|
|
int startPos[2];
|
||
|
|
enum direction dir;
|
||
|
|
} BLIZZARD;
|
||
|
|
|
||
|
|
int moves[5][2] = {
|
||
|
|
{1,0},
|
||
|
|
{0,1},
|
||
|
|
{-1,0},
|
||
|
|
{0,-1},
|
||
|
|
{0,0}
|
||
|
|
};
|
||
|
|
|
||
|
|
int dist(int [2], int [2]);
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
char buf[BUFFER_SIZE], *p, c;
|
||
|
|
memset(buf, 0, BUFFER_SIZE);
|
||
|
|
p = buf;
|
||
|
|
int y = 0, x = 0;
|
||
|
|
int map[MAX_MAP_SIZE][MAX_MAP_SIZE];
|
||
|
|
int startPos[2], endPos[2];
|
||
|
|
BLIZZARD blizzards[MAX_BLIZZARDS];
|
||
|
|
int blizzard_count = 0;
|
||
|
|
|
||
|
|
while ((c = getchar()) != EOF) {
|
||
|
|
*p++ = c;
|
||
|
|
if (c == '\n') {
|
||
|
|
p = buf;
|
||
|
|
while (*p != '\n') {
|
||
|
|
if (p-buf+1 > x) x = p - buf + 1;
|
||
|
|
if (*p == '#') {
|
||
|
|
map[p-buf][y] = 1;
|
||
|
|
} else if (*p == '.') {
|
||
|
|
map[p-buf][y] = 0;
|
||
|
|
if (y == 0) {
|
||
|
|
startPos[0] = p - buf;
|
||
|
|
startPos[1] = y;
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
blizzards[blizzard_count].startPos[0] = p - buf;
|
||
|
|
blizzards[blizzard_count].startPos[1] = y;
|
||
|
|
switch (*p) {
|
||
|
|
case '>':
|
||
|
|
blizzards[blizzard_count].dir = RIGHT;
|
||
|
|
break;
|
||
|
|
case 'v':
|
||
|
|
blizzards[blizzard_count].dir = DOWN;
|
||
|
|
break;
|
||
|
|
case '<':
|
||
|
|
blizzards[blizzard_count].dir = LEFT;
|
||
|
|
break;
|
||
|
|
case '^':
|
||
|
|
blizzards[blizzard_count].dir = UP;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
blizzard_count++;
|
||
|
|
}
|
||
|
|
p++;
|
||
|
|
}
|
||
|
|
y++;
|
||
|
|
memset(buf, 0, BUFFER_SIZE);
|
||
|
|
p = buf;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
// Get exit point
|
||
|
|
for (int i = 0; i < x; i++) {
|
||
|
|
if (map[i][y-1] == 0) {
|
||
|
|
endPos[0] = i;
|
||
|
|
endPos[1] = y - 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
int times[3];
|
||
|
|
int (*fifo)[3], fifo_count;
|
||
|
|
fifo = (int(*)[3])malloc(FIFO_MAX * sizeof(int[3]));
|
||
|
|
|
||
|
|
fifo[0][0] = startPos[0];
|
||
|
|
fifo[0][1] = startPos[1];
|
||
|
|
fifo[0][2] = 0;
|
||
|
|
fifo_count++;
|
||
|
|
|
||
|
|
// We will calculate the blizzardmap at each timepoint
|
||
|
|
int ***blizzardMap = (int***)malloc(MAX_BLIZZARDS_HISTORY * sizeof(int**));
|
||
|
|
for (int i = 0; i < MAX_BLIZZARDS_HISTORY; i++) {
|
||
|
|
blizzardMap[i] = (int**)malloc(x * sizeof(int*));
|
||
|
|
for (int j = 0; j < x; j++) {
|
||
|
|
blizzardMap[i][j] = (int*)malloc(y * sizeof(int));
|
||
|
|
memset(blizzardMap[i][j], 0, y * sizeof(int));
|
||
|
|
}
|
||
|
|
}
|
||
|
|
int blizzard_history_count = 0;
|
||
|
|
for (;;) {
|
||
|
|
if (fifo_count == 0) {
|
||
|
|
printf("PROBLEM\n");
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
// Pop next element from FIFO
|
||
|
|
int currPos[2], currTime;
|
||
|
|
currPos[0] = fifo[0][0];
|
||
|
|
currPos[1] = fifo[0][1];
|
||
|
|
currTime = fifo[0][2];
|
||
|
|
|
||
|
|
fifo_count--;
|
||
|
|
if (currPos[0] == endPos[0] && currPos[1] == endPos[1]) {
|
||
|
|
times[0] = currTime;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Shift back elements
|
||
|
|
for (int i = 0; i < fifo_count; i++) {
|
||
|
|
fifo[i][0] = fifo[i+1][0];
|
||
|
|
fifo[i][1] = fifo[i+1][1];
|
||
|
|
fifo[i][2] = fifo[i+1][2];
|
||
|
|
}
|
||
|
|
|
||
|
|
// Calculate each blizzard's position at currTime + 1
|
||
|
|
if (blizzard_history_count < currTime + 1) {
|
||
|
|
for (int j = 0; j < blizzard_count; j++) {
|
||
|
|
int newX, newY;
|
||
|
|
if (moves[blizzards[j].dir][0] >= 0) {
|
||
|
|
newX = 1 + ((blizzards[j].startPos[0] + (currTime+1) * (moves[blizzards[j].dir][0]) - 1) % (x-2));
|
||
|
|
} else {
|
||
|
|
newX = (x-2) - (((x-2) - blizzards[j].startPos[0] + (currTime+1) * abs(moves[blizzards[j].dir][0])) % (x-2));
|
||
|
|
}
|
||
|
|
if (moves[blizzards[j].dir][1] >= 0) {
|
||
|
|
newY = 1 + ((blizzards[j].startPos[1] + (currTime+1) * (moves[blizzards[j].dir][1]) - 1) % (y-2));
|
||
|
|
} else {
|
||
|
|
newY = (y-2) - (((y-2) - blizzards[j].startPos[1] + (currTime+1) * abs(moves[blizzards[j].dir][1])) % (y-2));
|
||
|
|
}
|
||
|
|
blizzardMap[currTime+1][newX][newY] = 1;
|
||
|
|
}
|
||
|
|
blizzard_history_count++;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Check each direction from position
|
||
|
|
for (int i = 0; i < 5; i++) {
|
||
|
|
int xp = currPos[0] + moves[i][0];
|
||
|
|
int yp = currPos[1] + moves[i][1];
|
||
|
|
|
||
|
|
// Hitting a wall or walking off the map is not healthy
|
||
|
|
if (yp < 0 || map[xp][yp] == 1) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// We cannot step on a tile where there will be a blizzard
|
||
|
|
// the next round
|
||
|
|
if (blizzardMap[currTime+1][xp][yp]) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Stepping back to the entry point is pointless
|
||
|
|
if (xp == startPos[0] && yp == startPos[1] && i != 4) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// There's no need to check the same position twice in the same round
|
||
|
|
int inFifo = 0;
|
||
|
|
for (int j = 0; j < fifo_count; j++) {
|
||
|
|
if (fifo[j][0] == xp && fifo[j][1] == yp && fifo[j][2] == currTime + 1) {
|
||
|
|
inFifo = 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (inFifo) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
fifo[fifo_count][0] = xp;
|
||
|
|
fifo[fifo_count][1] = yp;
|
||
|
|
fifo[fifo_count][2] = currTime + 1;
|
||
|
|
fifo_count++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
printf("To the end: %i\n", times[0]);
|
||
|
|
|
||
|
|
// Reset FIFO
|
||
|
|
fifo_count = 0;
|
||
|
|
|
||
|
|
fifo[0][0] = endPos[0];
|
||
|
|
fifo[0][1] = endPos[1];
|
||
|
|
fifo[0][2] = times[0];
|
||
|
|
fifo_count++;
|
||
|
|
|
||
|
|
for (;;) {
|
||
|
|
if (fifo_count == 0) {
|
||
|
|
printf("PROBLEM\n");
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
// Pop next element from FIFO
|
||
|
|
int currPos[2], currTime;
|
||
|
|
currPos[0] = fifo[0][0];
|
||
|
|
currPos[1] = fifo[0][1];
|
||
|
|
currTime = fifo[0][2];
|
||
|
|
|
||
|
|
fifo_count--;
|
||
|
|
if (currPos[0] == startPos[0] && currPos[1] == startPos[1]) {
|
||
|
|
times[1] = currTime;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Shift back elements
|
||
|
|
for (int i = 0; i < fifo_count; i++) {
|
||
|
|
fifo[i][0] = fifo[i+1][0];
|
||
|
|
fifo[i][1] = fifo[i+1][1];
|
||
|
|
fifo[i][2] = fifo[i+1][2];
|
||
|
|
}
|
||
|
|
|
||
|
|
// Calculate each blizzard's position at currTime + 1
|
||
|
|
if (blizzard_history_count < currTime + 1) {
|
||
|
|
for (int j = 0; j < blizzard_count; j++) {
|
||
|
|
int newX, newY;
|
||
|
|
if (moves[blizzards[j].dir][0] >= 0) {
|
||
|
|
newX = 1 + ((blizzards[j].startPos[0] + (currTime+1) * (moves[blizzards[j].dir][0]) - 1) % (x-2));
|
||
|
|
} else {
|
||
|
|
newX = (x-2) - (((x-2) - blizzards[j].startPos[0] + (currTime+1) * abs(moves[blizzards[j].dir][0])) % (x-2));
|
||
|
|
}
|
||
|
|
if (moves[blizzards[j].dir][1] >= 0) {
|
||
|
|
newY = 1 + ((blizzards[j].startPos[1] + (currTime+1) * (moves[blizzards[j].dir][1]) - 1) % (y-2));
|
||
|
|
} else {
|
||
|
|
newY = (y-2) - (((y-2) - blizzards[j].startPos[1] + (currTime+1) * abs(moves[blizzards[j].dir][1])) % (y-2));
|
||
|
|
}
|
||
|
|
blizzardMap[currTime+1][newX][newY] = 1;
|
||
|
|
}
|
||
|
|
blizzard_history_count++;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Check each direction from position
|
||
|
|
for (int i = 0; i < 5; i++) {
|
||
|
|
int xp = currPos[0] + moves[i][0];
|
||
|
|
int yp = currPos[1] + moves[i][1];
|
||
|
|
|
||
|
|
// Hitting a wall or walking off the map is not healthy
|
||
|
|
if (yp == y || map[xp][yp] == 1) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// We cannot step on a tile where there will be a blizzard
|
||
|
|
// the next round
|
||
|
|
if (blizzardMap[currTime+1][xp][yp]) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Stepping back to the entry point is pointless
|
||
|
|
if (xp == endPos[0] && yp == endPos[1] && i != 4) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// There's no need to check the same position twice in the same round
|
||
|
|
int inFifo = 0;
|
||
|
|
for (int j = 0; j < fifo_count; j++) {
|
||
|
|
if (fifo[j][0] == xp && fifo[j][1] == yp && fifo[j][2] == currTime + 1) {
|
||
|
|
inFifo = 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (inFifo) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
fifo[fifo_count][0] = xp;
|
||
|
|
fifo[fifo_count][1] = yp;
|
||
|
|
fifo[fifo_count][2] = currTime + 1;
|
||
|
|
fifo_count++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
printf("To the start: %i\n", times[1]);
|
||
|
|
|
||
|
|
fifo_count = 0;
|
||
|
|
|
||
|
|
fifo[0][0] = startPos[0];
|
||
|
|
fifo[0][1] = startPos[1];
|
||
|
|
fifo[0][2] = times[1];
|
||
|
|
fifo_count++;
|
||
|
|
for (;;) {
|
||
|
|
if (fifo_count == 0) {
|
||
|
|
printf("PROBLEM\n");
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
// Pop next element from FIFO
|
||
|
|
int currPos[2], currTime;
|
||
|
|
currPos[0] = fifo[0][0];
|
||
|
|
currPos[1] = fifo[0][1];
|
||
|
|
currTime = fifo[0][2];
|
||
|
|
|
||
|
|
fifo_count--;
|
||
|
|
if (currPos[0] == endPos[0] && currPos[1] == endPos[1]) {
|
||
|
|
times[2] = currTime;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Shift back elements
|
||
|
|
for (int i = 0; i < fifo_count; i++) {
|
||
|
|
fifo[i][0] = fifo[i+1][0];
|
||
|
|
fifo[i][1] = fifo[i+1][1];
|
||
|
|
fifo[i][2] = fifo[i+1][2];
|
||
|
|
}
|
||
|
|
|
||
|
|
// Calculate each blizzard's position at currTime + 1
|
||
|
|
if (blizzard_history_count < currTime + 1) {
|
||
|
|
for (int j = 0; j < blizzard_count; j++) {
|
||
|
|
int newX, newY;
|
||
|
|
if (moves[blizzards[j].dir][0] >= 0) {
|
||
|
|
newX = 1 + ((blizzards[j].startPos[0] + (currTime+1) * (moves[blizzards[j].dir][0]) - 1) % (x-2));
|
||
|
|
} else {
|
||
|
|
newX = (x-2) - (((x-2) - blizzards[j].startPos[0] + (currTime+1) * abs(moves[blizzards[j].dir][0])) % (x-2));
|
||
|
|
}
|
||
|
|
if (moves[blizzards[j].dir][1] >= 0) {
|
||
|
|
newY = 1 + ((blizzards[j].startPos[1] + (currTime+1) * (moves[blizzards[j].dir][1]) - 1) % (y-2));
|
||
|
|
} else {
|
||
|
|
newY = (y-2) - (((y-2) - blizzards[j].startPos[1] + (currTime+1) * abs(moves[blizzards[j].dir][1])) % (y-2));
|
||
|
|
}
|
||
|
|
blizzardMap[currTime+1][newX][newY] = 1;
|
||
|
|
}
|
||
|
|
blizzard_history_count++;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Check each direction from position
|
||
|
|
for (int i = 0; i < 5; i++) {
|
||
|
|
int xp = currPos[0] + moves[i][0];
|
||
|
|
int yp = currPos[1] + moves[i][1];
|
||
|
|
|
||
|
|
// Hitting a wall or walking off the map is not healthy
|
||
|
|
if (yp < 0 || map[xp][yp] == 1) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// We cannot step on a tile where there will be a blizzard
|
||
|
|
// the next round
|
||
|
|
if (blizzardMap[currTime+1][xp][yp]) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Stepping back to the entry point is pointless
|
||
|
|
if (xp == startPos[0] && yp == startPos[1] && i != 4) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
// There's no need to check the same position twice in the same round
|
||
|
|
int inFifo = 0;
|
||
|
|
for (int j = 0; j < fifo_count; j++) {
|
||
|
|
if (fifo[j][0] == xp && fifo[j][1] == yp && fifo[j][2] == currTime + 1) {
|
||
|
|
inFifo = 1;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (inFifo) {
|
||
|
|
continue;
|
||
|
|
}
|
||
|
|
|
||
|
|
fifo[fifo_count][0] = xp;
|
||
|
|
fifo[fifo_count][1] = yp;
|
||
|
|
fifo[fifo_count][2] = currTime + 1;
|
||
|
|
fifo_count++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
printf("Back to the end: %i\n", times[2]);
|
||
|
|
for (int i = 0; i < MAX_BLIZZARDS_HISTORY; i++) {
|
||
|
|
for (int j = 0; j < x; j++) {
|
||
|
|
free(blizzardMap[i][j]);
|
||
|
|
}
|
||
|
|
free(blizzardMap[i]);
|
||
|
|
}
|
||
|
|
free(blizzardMap);
|
||
|
|
free(fifo);
|
||
|
|
}
|
||
|
|
|
||
|
|
int dist(int one[2], int two[2]) {
|
||
|
|
return abs(one[0] - two[0]) + abs(one[1] - two[1]);
|
||
|
|
}
|