--- Day 11: Seating System ---

#include <iostream>
#include <algorithm>
#include <string>

bool ApplyRulesP1(std::string& map, unsigned int width, unsigned int height)
{
    bool change = false;
    std::string apply = map;

    for (unsigned int x = 0; x < width; x++)
    {
        for (unsigned int y = 0; y < height; y++)
        {
            char s = map[(y * width) + x];

            int occ = 0;
            if (x > 0           &&                      map[(y * width) + (x - 1)] == '#') occ++;
            if (x < width - 1   &&                      map[(y * width) + (x + 1)] == '#') occ++;
            if (y > 0           &&                      map[((y - 1) * width) + x] == '#') occ++;
            if (y < height - 1  &&                      map[((y + 1) * width) + x] == '#') occ++;
            if (x > 0           && y > 0 &&             map[((y - 1) * width) + (x - 1)] == '#') occ++;
            if (x < width - 1   && y > 0 &&             map[((y - 1) * width) + (x + 1)] == '#') occ++;
            if (x > 0           && y < height - 1 &&    map[((y + 1) * width) + (x - 1)] == '#') occ++;
            if (x < width - 1   && y < height - 1 &&    map[((y + 1) * width) + (x + 1)] == '#') occ++;

            if (s == 'L' && occ == 0)
            {
                apply[(y * width) + x] = '#';
                change = true;
            }
            else if (s == '#' && occ >= 4)
            {
                apply[(y * width) + x] = 'L';
                change = true;
            }
        }
    }

    if (change)
    {
        map = apply;
        return true;
    }

    return change;
}

bool FindAdjacentSeat(const std::string& map, int x, int y, int dirX, int dirY, unsigned int width, unsigned int height)
{
    x += dirX;
    y += dirY;
    while (x >= 0 && y >= 0 && x < width && y < height)
    {
        if (map[(y * width) + x] == '#')
            return true;

        if (map[(y * width) + x] == 'L')
            return false;

        x += dirX;
        y += dirY;
    }

    return false;
}

bool ApplyRulesP2(std::string& map, unsigned int width, unsigned int height)
{
    bool change = false;
    std::string apply = map;

    for (unsigned int x = 0; x < width; x++)
    {
        for (unsigned int y = 0; y < height; y++)
        {
            char s = map[(y * width) + x];

            int occ = 0;
            if (FindAdjacentSeat(map, x, y, -1, 0, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, +1, 0, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, 0, -1, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, 0, +1, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, -1, -1, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, +1, -1, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, -1, +1, width, height)) occ++;
            if (FindAdjacentSeat(map, x, y, +1, +1, width, height)) occ++;

            if (s == 'L' && occ == 0)
            {
                apply[(y * width) + x] = '#';
                change = true;
            }
            else if (s == '#' && occ >= 5)
            {
                apply[(y * width) + x] = 'L';
                change = true;
            }
        }
    }

    if (change)
    {
        map = apply;
        return true;
    }

    return change;
}

void PrintMap(const std::string& map, unsigned int width, unsigned int height)
{
    for (unsigned int y = 0; y < height; y++)
    {
        std::cout << map.substr(y * width, width) << std::endl;
    }
}

int main()
{
    unsigned int width = 0;
    unsigned int height = 0;

    std::string map;
    std::string text;
    while (getline(std::cin, text))
    {
        if (height > 0) //Removes any \n or \0 from the last trail sequence
            map.pop_back();

        map += text;
        height++;
        width = text.size();
    }

    //PrintMap(map, width, height);
    //std::cout << std::endl;
    while (ApplyRulesP2(map, width, height))
    {
        //PrintMap(map, width, height);
        //std::cout << std::endl;
    }

    std::cout << "Number of occupied seats: " << std::count(map.begin(), map.end(), '#') << std::endl;

    return 0;
}