#include <iostream>
#include <array>
#include <cstdint>
#include <fstream>
#include <iterator>
#include <bitset>

#define WIDTH 54
#define HEIGHT 54

using map_t = std::array<std::array<uint8_t, WIDTH>, HEIGHT>;

struct Point
{
    int_fast8_t Row;
    int_fast8_t Col;
};

struct sols_t
{
    std::bitset<WIDTH*HEIGHT> bits;
    void emplace(Point point)
    {
        bits.set(point.Row * WIDTH + point.Col);
    }
    int size() const
    {
        return bits.count();
    }
    void clear()
    {
        bits.reset();
    }
};

void load_map(map_t& map, const char* filepath)
{
    std::fstream in(filepath);
    std::istreambuf_iterator iter(in);
    for (auto& row : map)
    {
        for (auto& cell : row)
        {
            cell = *(iter++) - '0';
        }
        iter++;
    }
}

void quick_branch(const map_t& map, sols_t& terminals, Point init)
{
    std::array<int_fast8_t, 9> path;
    int_fast8_t height = 0;
    path[0] = 0;
    Point pos = init;
    while (height >= 0)
    {
        // const auto& pos = path[height].pos;
        switch (path[height]++)
        {
            case 0:
                if (pos.Row > 0 && map[pos.Row-1][pos.Col] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({static_cast<int_fast8_t>(pos.Row-1), pos.Col});
                    else
                    {
                        path[++height] = 0;
                        pos.Row--;
                    }
                }
                break;
            case 1:
                if (pos.Col < WIDTH-1 && map[pos.Row][pos.Col+1] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({pos.Row, static_cast<int_fast8_t>(pos.Col+1)});
                    else
                    {
                        path[++height] = 0;
                        pos.Col++;
                    }
                }
                break;
            case 2:
                if (pos.Row < HEIGHT-1 && map[pos.Row+1][pos.Col] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({static_cast<int_fast8_t>(pos.Row+1), pos.Col});
                    else
                    {
                        path[++height] = 0;
                        pos.Row++;
                    }
                }
                break;
            case 3:
                if (pos.Col > 0 && map[pos.Row][pos.Col-1] == height+1)
                {
                    if (height == 8)
                        terminals.emplace({pos.Row, static_cast<int_fast8_t>(pos.Col-1)});
                    else
                    {
                        path[++height] = 0;
                        pos.Col--;
                    }
                }
                break;
            default:
                if (height > 0)
                    //remember that the previous path was already incremented
                    switch (path[height-1])
                    {
                        case 1:
                            pos.Row++;
                            break;
                        case 2:
                            pos.Col--;
                            break;
                        case 3:
                            pos.Row--;
                            break;
                        case 4:
                            pos.Col++;
                            break;
                    }
                height--;
                break;
        }
    }
}

int quick_branch2(const map_t& map, Point init)
{
    std::array<int_fast8_t, 9> path;
    int_fast8_t height = 0;
    path[0] = 0;
    int total = 0;
    Point pos = init;
    while (height >= 0)
    {
        switch (path[height]++)
        {
            case 0:
                if (pos.Row > 0 && map[pos.Row-1][pos.Col] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Row--;
                    }
                }
                break;
            case 1:
                if (pos.Col < WIDTH-1 && map[pos.Row][pos.Col+1] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Col++;
                    }
                }
                break;
            case 2:
                if (pos.Row < HEIGHT-1 && map[pos.Row+1][pos.Col] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Row++;
                    }
                }
                break;
            case 3:
                if (pos.Col > 0 && map[pos.Row][pos.Col-1] == height+1)
                {
                    if (height == 8)
                        total++;
                    else
                    {
                        path[++height] = 0;
                        pos.Col--;
                    }
                }
                break;
            default:
                if (height > 0)
                    //remember that the previous path was already incremented
                    switch (path[height-1])
                    {
                        case 1:
                            pos.Row++;
                            break;
                        case 2:
                            pos.Col--;
                            break;
                        case 3:
                            pos.Row--;
                            break;
                        case 4:
                            pos.Col++;
                            break;
                    }
                height--;
                break;
        }
    }
    return total;
}

void main1(const map_t& map)
{
    int total = 0;
    sols_t terminals;
    terminals.clear();
    for (int8_t r = 0; r < map.size(); r++)
    {
        for (int8_t c = 0; c < map[r].size(); c++)
        {
            if (map[r][c] == 0)
            {
                quick_branch(map, terminals, {r, c});
                total += terminals.size();
                terminals.clear();
            }
        }
    }
    std::cout << "Part1 " << total << std::endl;
}

void main2(const map_t& map)
{
    int32_t total = 0;
    for (int8_t r = 0; r < map.size(); r++)
    {
        for (int8_t c = 0; c < map[r].size(); c++)
        {
            if (map[r][c] == 0)
            {
                total += quick_branch2(map, {r, c});
            }
        }
    }
    std::cout << "Part2 " << total << std::endl;
}

int main()
{
    map_t map;
    load_map(map, "10.txt");
    main1(map);
    main2(map);
    return 0;
}