#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUFFER_SIZE 256
#define MAP_MAX_SIZE 1024
#define MAX_ELVES 4*1024
#define ROUNDS 10000

typedef struct elf {
    int position[2]; 
    int nextPosition[2];
} ELF;

typedef struct linkedDirection {
    int (*dir)[2];
    struct linkedDirection *next;
    char name[16];
} LINKEDDIRECTION;

int directions[4][3][2] = {
    {{0, -1}, {1, -1}, {-1, -1}},
    {{0, 1}, {-1, 1}, {1, 1}},
    {{-1, 0}, {-1, -1}, {-1, 1}},
    {{1, 0}, {1, -1}, {1, 1}}
};

int main() {
    char buf[BUFFER_SIZE], *p, c;
    memset(buf, 0, BUFFER_SIZE);
    p = buf;
    int y = 0, x = 0;
    ELF elves[MAX_ELVES];
    int elf_count = 0;

    while ((c = getchar()) != EOF) {
        *p++ = c;
        if (c == '\n') {
            p = buf;
            while (*p != '\n' && *p != EOF) {
                if ((p-buf+1) > x) x = (p-buf+1);
                if (*p == '#') {
                    elves[elf_count].position[0] = (p-buf);
                    elves[elf_count].position[1] = y;
                    elf_count++;
                }
                p++;
            }
            y++;
            memset(buf, 0, BUFFER_SIZE);
            p = buf;
        }
    }

    // Set up a circular direction list
    LINKEDDIRECTION dirs[4];
    dirs[0].dir = directions[0];
    sprintf(dirs[0].name, "NORTH");
    dirs[0].next = &dirs[1];
    dirs[1].dir = directions[1];
    sprintf(dirs[1].name, "SOUTH");
    dirs[1].next = &dirs[2];
    dirs[2].dir = directions[2];
    sprintf(dirs[2].name, "WEST");
    dirs[2].next = &dirs[3];
    dirs[3].dir = directions[3];
    sprintf(dirs[3].name, "EAST");
    dirs[3].next = &dirs[0];

    LINKEDDIRECTION *curr = &dirs[0];

    // Put each elf on a map
    int **map;
    map = (int **)malloc(MAP_MAX_SIZE * sizeof(int*));
    for (int i = 0; i < MAP_MAX_SIZE; i++) {
        map[i] = (int*)malloc(MAP_MAX_SIZE * sizeof(int));
        memset(map[i], 0, MAP_MAX_SIZE * sizeof(int));
    }

    int ref[2];
    ref[0] = (MAP_MAX_SIZE - x)/2;
    ref[1] = (MAP_MAX_SIZE - y)/2;
    for (int i = 0; i < elf_count; i++) {
        map[elves[i].position[0]+ref[0]][elves[i].position[1]+ref[1]] = 1;
    }

    int izegmozog = 1;
    // Simulate 10 rounds
    for (int i = 0; i < ROUNDS; i++) {
        // DEBUG
//        int minX = elves[0].position[0], maxX = elves[0].position[0], minY = elves[0].position[1], maxY = elves[0].position[1];
//
//        for (int i = 0; i < elf_count; i++) {
//            if (minX > elves[i].position[0]) {
//                minX = elves[i].position[0];
//            }
//            if (maxX < elves[i].position[0]) {
//                maxX = elves[i].position[0];
//            }
//            if (minY > elves[i].position[1]) {
//                minY = elves[i].position[1];
//            }
//            if (maxY < elves[i].position[1]) {
//                maxY = elves[i].position[1];
//            }
//        }
//        
//        printf("%i,%i %i,%i\n", minX, minY, maxX, maxY);
//        for (int i = minY - 1; i <= maxY + 1; i++) {
//            for (int j = minX - 1; j <= maxX + 1; j++) {
//                if (map[j+ref[0]][i+ref[1]] == 1) {
//                    printf("#");
//                } else {
//                    printf(".");
//                }
//            }
//            printf("\n");
//        }
        // DEBUG END
        int **moveMap;
        moveMap = (int **)malloc(MAP_MAX_SIZE * sizeof(int*));
        for (int i = 0; i < MAP_MAX_SIZE; i++) {
            moveMap[i] = (int*)malloc(MAP_MAX_SIZE * sizeof(int));
            memset(moveMap[i], 0, MAP_MAX_SIZE * sizeof(int));
        }

        // PLANNING PHASE
        // Each elf
        for (int j = 0; j < elf_count; j++) {
            // Scan each direction
            LINKEDDIRECTION dirr = *curr;
            int openDirections = 0;
            int firstOpen[2] = {-9999, -9999};
            for (int k = 0; k < 4; k++) {
                int open = 1;
                for (int l = 0; l < 3; l++) {
                    if (map[elves[j].position[0]+ref[0]+dirr.dir[l][0]][elves[j].position[1]+ref[1]+dirr.dir[l][1]] == 1) {
                        open = 0;
                        break;
                    }
                }
                if (open) {
                    if (firstOpen[0] == -9999 && firstOpen[1] == -9999) {
                        firstOpen[0] = elves[j].position[0]+dirr.dir[0][0];
                        firstOpen[1] = elves[j].position[1]+dirr.dir[0][1];
                    }
                    openDirections++;
                }
                dirr = *dirr.next;
            }
            if (openDirections == 4 || openDirections == 0) {
                // No need to move/Can't move
                elves[j].nextPosition[0] = elves[j].position[0];
                elves[j].nextPosition[1] = elves[j].position[1];
            } else {
                elves[j].nextPosition[0] = firstOpen[0];
                elves[j].nextPosition[1] = firstOpen[1];
            }
            moveMap[elves[j].nextPosition[0]+ref[0]][elves[j].nextPosition[1]+ref[1]]++;
        }

        izegmozog = 0;
        // MOVE PHASE
        for (int j = 0; j < elf_count; j++) {
            // Should I stay or should I go?
            if (moveMap[elves[j].nextPosition[0]+ref[0]][elves[j].nextPosition[1]+ref[1]] != 1) {
                continue;
            }

            if (elves[j].position[0] != elves[j].nextPosition[0] || elves[j].position[1] != elves[j].nextPosition[1]) {
                izegmozog = 1;
            }
            // Remove from old position on the map
            map[elves[j].position[0]+ref[0]][elves[j].position[1]+ref[1]] = 0;

            // Add on new position
            map[elves[j].nextPosition[0]+ref[0]][elves[j].nextPosition[1]+ref[1]] = 1;

            // Change elf data
            elves[j].position[0] = elves[j].nextPosition[0];
            elves[j].position[1] = elves[j].nextPosition[1];
        }

        for (int j = 0; j < MAP_MAX_SIZE; j++) {
            free(moveMap[j]);
        }
        free(moveMap);

        curr = curr->next;

        if (!izegmozog) {
            printf("Rounds to stabilize: %i\n", i+1);
            break;
        }
    }

    int minX = elves[0].position[0], maxX = elves[0].position[0], minY = elves[0].position[1], maxY = elves[0].position[1];

    for (int i = 0; i < elf_count; i++) {
        if (minX > elves[i].position[0]) {
            minX = elves[i].position[0];
        }
        if (maxX < elves[i].position[0]) {
            maxX = elves[i].position[0];
        }
        if (minY > elves[i].position[1]) {
            minY = elves[i].position[1];
        }
        if (maxY < elves[i].position[1]) {
            maxY = elves[i].position[1];
        }
    }
    
    int sum = 0;
    for (int i = minY; i <= maxY; i++) {
        for (int j = minX; j <= maxX; j++) {
            if (map[j+ref[0]][i+ref[1]] != 1) {
                sum++;
            }
        }
    }
    printf("Rectangle empty spaces after round %i: %i\n", ROUNDS, sum);

    for (int i = 0; i < MAP_MAX_SIZE; i++) {
        free(map[i]);
    }
    free(map);
}