262 lines
8.1 KiB
C
262 lines
8.1 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
#define MAX_DIMENSION 1024
|
|
#define MAX_MOVES 1024*1024
|
|
|
|
typedef enum tile {
|
|
EMPTY,
|
|
WALL,
|
|
BOX,
|
|
ROBOT
|
|
} tile_t;
|
|
|
|
typedef struct object {
|
|
tile_t type;
|
|
int pos[2];
|
|
} object_t;
|
|
|
|
int can_move(object_t ***map, int rows, int columns, int x, int y, int dir[2]);
|
|
void move(object_t ***map, int rows, int columns, int x, int y, int dir[2]);
|
|
|
|
int main() {
|
|
char c;
|
|
|
|
object_t ***map = calloc(MAX_DIMENSION, sizeof(map[0]));
|
|
int rows = 0, columns, i = 0;
|
|
map[0] = calloc(MAX_DIMENSION, sizeof(object_t*));
|
|
|
|
int reading_map = 1;
|
|
|
|
int (*moves)[2] = calloc(MAX_MOVES, sizeof(moves[0]));
|
|
int move_count = 0;
|
|
|
|
int robot_pos[2];
|
|
|
|
while ((c = getchar()) != EOF) {
|
|
if (reading_map) {
|
|
if (i == 0 && c == '\n') {
|
|
reading_map = 0;
|
|
continue;
|
|
}
|
|
|
|
switch (c) {
|
|
case '.':
|
|
{
|
|
object_t *obj = calloc(1, sizeof(obj[0]));
|
|
obj->type = EMPTY;
|
|
obj->pos[0] = rows;
|
|
obj->pos[1] = i;
|
|
map[rows][i] = obj;
|
|
object_t *obj2 = calloc(1, sizeof(obj2[0]));
|
|
obj2->type = EMPTY;
|
|
obj2->pos[0] = rows;
|
|
obj2->pos[1] = ++i;
|
|
map[rows][i] = obj2;
|
|
}
|
|
break;
|
|
case '#':
|
|
{
|
|
object_t *obj = calloc(1, sizeof(obj[0]));
|
|
obj->type = WALL;
|
|
obj->pos[0] = rows;
|
|
obj->pos[1] = i;
|
|
map[rows][i] = obj;
|
|
map[rows][++i] = obj;
|
|
}
|
|
break;
|
|
case 'O':
|
|
{
|
|
object_t *obj = calloc(1, sizeof(obj[0]));
|
|
obj->type = BOX;
|
|
obj->pos[0] = rows;
|
|
obj->pos[1] = i;
|
|
map[rows][i] = obj;
|
|
map[rows][++i] = obj;
|
|
}
|
|
break;
|
|
case '@':
|
|
{
|
|
object_t *obj = calloc(1, sizeof(obj[0]));
|
|
obj->type = ROBOT;
|
|
obj->pos[0] = rows;
|
|
obj->pos[1] = i;
|
|
map[rows][i] = obj;
|
|
robot_pos[0] = rows;
|
|
robot_pos[1] = i;
|
|
object_t *obj2 = calloc(1, sizeof(obj2[0]));
|
|
obj2->type = EMPTY;
|
|
obj2->pos[0] = rows;
|
|
obj2->pos[1] = ++i;
|
|
map[rows][i] = obj2;
|
|
}
|
|
break;
|
|
}
|
|
|
|
i++;
|
|
if (c != '\n') {
|
|
continue;
|
|
}
|
|
|
|
columns = i - 1;
|
|
i = 0;
|
|
rows++;
|
|
map[rows] = calloc(MAX_DIMENSION, sizeof(object_t*));
|
|
} else {
|
|
switch(c) {
|
|
case '>':
|
|
moves[move_count][0] = 0;
|
|
moves[move_count][1] = 1;
|
|
move_count++;
|
|
break;
|
|
case '<':
|
|
moves[move_count][0] = 0;
|
|
moves[move_count][1] = -1;
|
|
move_count++;
|
|
break;
|
|
case 'v':
|
|
moves[move_count][0] = 1;
|
|
moves[move_count][1] = 0;
|
|
move_count++;
|
|
break;
|
|
case '^':
|
|
moves[move_count][0] = -1;
|
|
moves[move_count][1] = 0;
|
|
move_count++;
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (i = 0; i < move_count; i++) {
|
|
if (can_move(map, rows, columns, robot_pos[0], robot_pos[1], moves[i])) {
|
|
move(map, rows, columns, robot_pos[0], robot_pos[1], moves[i]);
|
|
robot_pos[0] += moves[i][0];
|
|
robot_pos[1] += moves[i][1];
|
|
}
|
|
}
|
|
|
|
int sum = 0;
|
|
for (i = 0; i < rows; i++) {
|
|
for (int j = 0; j < columns; j++) {
|
|
if (map[i][j]->type == BOX && map[i][j]->pos[0] == i && map[i][j]->pos[1] == j) {
|
|
sum += 100 * i + j;
|
|
}
|
|
}
|
|
}
|
|
|
|
for (i = 0; i < rows + 1; i++) {
|
|
free(map[i]);
|
|
}
|
|
free(map);
|
|
free(moves);
|
|
|
|
printf("%i\n", sum);
|
|
}
|
|
|
|
int can_move(object_t ***map, int rows, int columns, int x, int y, int dir[2]) {
|
|
// Walls cannot move
|
|
if (map[x][y]->type == WALL) {
|
|
return 0;
|
|
}
|
|
|
|
// Empty space can be filled
|
|
if (map[x][y]->type == EMPTY) {
|
|
return 1;
|
|
}
|
|
|
|
// A box/robot can move if the next tile is movable
|
|
int next_x = x + dir[0];
|
|
int next_y = y + dir[1];
|
|
// Cannot move out of the map although it should not be possible to reach this
|
|
if (next_x < 0 || next_y < 0 || next_x >= rows || next_y >= columns) {
|
|
return 0;
|
|
}
|
|
|
|
object_t *next_object = map[next_x][next_y];
|
|
|
|
if (next_object->type == WALL) {
|
|
return 0;
|
|
}
|
|
|
|
if (next_object->type == BOX) {
|
|
int can = 1;
|
|
if (map[x][y] != map[next_object->pos[0]][next_object->pos[1]]) {
|
|
can &= can_move(map, rows, columns, next_object->pos[0], next_object->pos[1], dir);
|
|
}
|
|
if (map[x][y] != map[next_object->pos[0]][next_object->pos[1] + 1]) {
|
|
can &= can_move(map, rows, columns, next_object->pos[0], next_object->pos[1] + 1, dir);
|
|
}
|
|
return can;
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
void move(object_t ***map, int rows, int columns, int x, int y, int dir[2]) {
|
|
// Walls cannot move
|
|
if (map[x][y]->type == WALL) {
|
|
return;
|
|
}
|
|
|
|
// Empty space can be filled
|
|
if (map[x][y]->type == EMPTY) {
|
|
free(map[x][y]);
|
|
return;
|
|
}
|
|
|
|
if (map[x][y]->type == BOX) {
|
|
int current_positions[2][2];
|
|
int next_positions[2][2];
|
|
current_positions[0][0] = map[x][y]->pos[0];
|
|
current_positions[0][1] = map[x][y]->pos[1];
|
|
current_positions[1][0] = map[x][y]->pos[0];
|
|
current_positions[1][1] = map[x][y]->pos[1] + 1;
|
|
next_positions[0][0] = current_positions[0][0] + dir[0];
|
|
next_positions[0][1] = current_positions[0][1] + dir[1];
|
|
next_positions[1][0] = current_positions[1][0] + dir[0];
|
|
next_positions[1][1] = current_positions[1][1] + dir[1];
|
|
if (map[x][y] != map[next_positions[0][0]][next_positions[0][1]]) {
|
|
move(map, rows, columns, next_positions[0][0], next_positions[0][1], dir);
|
|
}
|
|
if (map[x][y] != map[next_positions[1][0]][next_positions[1][1]]) {
|
|
move(map, rows, columns, next_positions[1][0], next_positions[1][1], dir);
|
|
}
|
|
// Move current
|
|
map[x][y]->pos[0] = next_positions[0][0];
|
|
map[x][y]->pos[1] = next_positions[0][1];
|
|
map[next_positions[0][0]][next_positions[0][1]] = map[x][y];
|
|
map[next_positions[1][0]][next_positions[1][1]] = map[x][y];
|
|
// Free up positions that were left
|
|
for (int i = 0; i < 2; i++) {
|
|
int left = 1;
|
|
for (int j = 0; j < 2; j++) {
|
|
if (next_positions[j][0] == current_positions[i][0] && next_positions[j][1] == current_positions[i][1]) {
|
|
left = 0;
|
|
break;
|
|
}
|
|
}
|
|
if (left) {
|
|
object_t *obj = calloc(1, sizeof(obj[0]));
|
|
obj->type = EMPTY;
|
|
obj->pos[0] = current_positions[i][0];
|
|
obj->pos[1] = current_positions[i][1];
|
|
map[obj->pos[0]][obj->pos[1]] = obj;
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
// Robot is a single unit
|
|
int next_x = x + dir[0];
|
|
int next_y = y + dir[1];
|
|
move(map, rows, columns, next_x, next_y, dir);
|
|
map[next_x][next_y] = map[x][y];
|
|
object_t *obj = calloc(1, sizeof(obj[0]));
|
|
obj->type = EMPTY;
|
|
obj->pos[0] = x;
|
|
obj->pos[1] = y;
|
|
map[obj->pos[0]][obj->pos[1]] = obj;
|
|
}
|