#include <cstdio>
#include <vector>
#include <cstdint>
#include "stb_image.h"
#include <unordered_set>
#include <algorithm>
#include <cassert>
#include <chrono>

enum Direction
{
    Up,
    Down,
    Left,
    Right,
};

struct Point
{
    int x, y;

};

bool operator==(const Point& a, const Point& b)
{
    return a.x == b.x && a.y == b.y;
}
bool operator!=(const Point& a, const Point& b)
{
    return !(a == b);
}

Point get_offset(int x, int y, Direction dir)
{
    switch (dir)
    {
    case Up: return { x, y - 1 };
    case Down: return { x, y + 1 };
    case Left: return { x - 1, y };
    case Right: return { x + 1, y };
    }

    return { x, y };
}

Direction get_opposite(Direction dir)
{
    switch (dir)
    {
    case Up: return Down;
    case Down: return Up;
    case Left: return Right;
    case Right: return Left;
    }
    return Up;
}

struct Freedoms
{
    Direction directions[4];
    uint16_t count;
};

struct Board
{
    enum EdgeState
    {
        EdgeEmpty = 0,
        EdgeWall = 1 << 0,
        EdgeLine = 1 << 1,
        EdgeDoor = 1 << 2,
    };

    enum CellState
    {
        CellEmpty,
        CellFullLine,
        CellHalfLine,
    };

    std::vector<EdgeState> horizontal_edges;
    std::vector<EdgeState> vertical_edges;
    std::vector<CellState> cell_states;

    bool half_finished = false;
    bool finished = false;
    Point half_finish_point;
    Point finish_point;

    EdgeState get_edge(int x, int y, Direction dir)
    {
        switch (dir)
        {
        case Up:
            return horizontal_edges[x + y * width];
        case Down:
            return horizontal_edges[x + (y + 1) * width];
        case Left:
            return vertical_edges[x + y * (width + 1)];
        case Right:
            return vertical_edges[x + 1 + y * (width + 1)];
        }
        return EdgeWall;
    }
    void set_edge(int x, int y, Direction dir, EdgeState edge)
    {
        switch (dir)
        {
        case Up:
            horizontal_edges[x + y * width] = edge;
            break;
        case Down:
            horizontal_edges[x + (y + 1) * width] = edge;
            break;
        case Left:
            vertical_edges[x + y * (width + 1)] = edge;
            break;
        case Right:
            vertical_edges[x + 1 + y * (width + 1)] = edge;
            break;
        }
    }

    CellState get_cell(int x, int y)
    {
        int linecount = 0;
        for (int i = 0; i < 4; i++)
        {
            EdgeState edge = get_edge(x, y, (Direction)i);
            if (edge == EdgeLine)
                linecount++;
        }
        switch (linecount)
        {
        case 0: return CellEmpty;
        case 1: return CellHalfLine;
        case 2: return CellFullLine;
        }
        return CellEmpty;
    }

    CellState get_neighbor_cell(int x, int y, Direction dir)
    {
        switch (dir)
        {
        case Up:
            return y > 0 ? get_cell(x, y - 1) : CellEmpty;
        case Down:
            return y + 1 < height ? get_cell(x, y + 1) : CellEmpty;
        case Left:
            return x > 0 ? get_cell(x - 1, y) : CellEmpty;
        case Right:
            return x + 1 < width ? get_cell(x + 1, y) : CellEmpty;
        }
        return CellEmpty;
    }

    int width, height;
};

bool operator==(const Board& a, const Board& b)
{
    return a.horizontal_edges == b.horizontal_edges && a.vertical_edges == b.vertical_edges;
}

struct BoardHash
{
    size_t operator()(const Board& b)
    {
        size_t hash = 0;
        for (unsigned i = 0; i < b.vertical_edges.size(); i++)
            hash ^= b.vertical_edges[i] + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        for (unsigned i = 0; i < b.horizontal_edges.size(); i++)
            hash ^= b.horizontal_edges[i] + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        return hash;
    }
};

Freedoms get_freedoms(Board& board, int x, int y)
{
    Freedoms freedoms = { };
    for (int i = 0; i < 4; i++)
    {
        Direction dir = (Direction)i;

        Board::EdgeState edge = board.get_edge(x, y, dir);
        if (edge != Board::EdgeEmpty && edge != Board::EdgeDoor)
            continue;

        Board::CellState cell = board.get_neighbor_cell(x, y, dir);
        if (cell == Board::CellFullLine)
            continue;

        freedoms.directions[freedoms.count++] = dir;
    }
    return freedoms;
}

enum SolveState
{
    SolveUnchanged = 0,
    SolveChanged = 1,
    SolveInvalid = 2,
};

enum SolveResult
{
    ResultSolved,
    ResultInvalid,
    ResultIndeterminate,
};

// Returns true if no cycles were found
bool follow_line(Board& board, int x, int y, Point* out = nullptr, int* outLen = nullptr, int last=-1)
{
    int cx = x, cy = y;
    int len = 0;
    while (true)
    {
        int i;
        for (i = 0; i < 4; i++)
        {
            if (i == last)
                continue;

            if (board.get_edge(cx, cy, (Direction)i) == Board::EdgeLine)
            {
                Point nextPoint = get_offset(cx, cy, (Direction)i);
                cx = nextPoint.x;
                cy = nextPoint.y;
                last = get_opposite((Direction)i);
                len++;
                break;
            }
        }

        if (i == 4 || cx < 0 || cy < 0 || cx >= board.width || cy >= board.height)
        {
            if (out)
            {
                out->x = cx;
                out->y = cy;
            }
            if (outLen)
                *outLen = len;
            return true;
        }

        if (x == cx && y == cy)
            return false;
    }
}

bool follow_line_on_edge(Board& board, int x, int y, Point* out, int* outLen)
{
    if (x < 0)
        return follow_line(board, x + 1, y, out, outLen, Left);
    if (y < 0)
        return follow_line(board, x, y + 1, out, outLen, Up);
    if (x >= board.width)
        return follow_line(board, x - 1, y, out, outLen, Right);
    if (y >= board.height)
        return follow_line(board, x, y - 1, out, outLen, Down);
    return false;
}

SolveState solve_one_freedom(Board& board)
{
    bool didSomething = false;
    for (int x = 0; x < board.width; x++)
    {
        for (int y = 0; y < board.height; y++)
        {
            Board::CellState cell = board.get_cell(x, y);

            if (cell != Board::CellHalfLine)
                continue;

            Freedoms freedoms = get_freedoms(board, x, y);
            if (freedoms.count == 1)
            {
                board.set_edge(x, y, freedoms.directions[0], Board::EdgeLine);
                didSomething = true;
                if (!follow_line(board, x, y))
                    return SolveInvalid;
            }
            else if (freedoms.count == 2)
            {
                for (int i = 0; i < 2; i++)
                {
                    bool isInvalid = false;

                    Board::CellState ncell = board.get_neighbor_cell(x, y, freedoms.directions[i]);
                    if (ncell == Board::CellHalfLine)
                    {

                        Point pos = get_offset(x, y, freedoms.directions[i]);
                        Point outPoint;
                        if (!follow_line(board, pos.x, pos.y, &outPoint))
                            return SolveInvalid;
                        if (outPoint.x == x && outPoint.y == y)
                        {
                            isInvalid = true;
                        }
                    }

                    Board::EdgeState nedge = board.get_edge(x, y, freedoms.directions[i]);
                    if (nedge == Board::EdgeDoor)
                    {
                        if (board.half_finished)
                        {
                            isInvalid = true;
                        }
                    }

                    if (isInvalid)
                    {
                        board.set_edge(x, y, freedoms.directions[(i + 1) % 2], Board::EdgeLine);
                        didSomething = true;
                        break;
                    }
                }
            }
            else if (freedoms.count == 0)
                return SolveInvalid;
        }
    }
    return didSomething ? SolveChanged : SolveUnchanged;
}

SolveState solve_two_freedoms(Board& board)
{
    bool didSomething = false;
    for (int x = 0; x < board.width; x++)
    {
        for (int y = 0; y < board.height; y++)
        {
            Board::CellState cell = board.get_cell(x, y);

            if (cell == Board::CellFullLine || cell == Board::CellHalfLine)
                continue;

            Freedoms freedoms = get_freedoms(board, x, y);

            if (freedoms.count == 0)
            {
                return SolveInvalid;
            }

            if (freedoms.count == 2)
            {
                board.set_edge(x, y, freedoms.directions[0], Board::EdgeLine);
                board.set_edge(x, y, freedoms.directions[1], Board::EdgeLine);

                if (!follow_line(board, x, y))
                    return SolveInvalid;

                didSomething = true;
            }
        }
    }
    return didSomething ? SolveChanged : SolveUnchanged;
}

SolveState solve_bouncing(Board& board)
{
    return SolveUnchanged;
}

SolveState solve_blocked_exits(Board& board)
{
    int linecount = 0;
    int doorcount = 0;

    struct EdgePos
    {
        int x, y;
        Direction dir;
    };

    EdgePos doors[2];
    Point linePos[2];

    auto process_edge = [&](int x, int y, Direction dir){
        Board::EdgeState edge = board.get_edge(x, y, dir);
        if (edge == Board::EdgeLine)
        {
            if (linecount < 2)
                linePos[linecount] = get_offset(x, y, dir);
            linecount++;
        }
        else if (edge == Board::EdgeDoor)
        {
            if (board.get_cell(x, y) == Board::CellFullLine)
                return;

            if (doorcount < 2)
                doors[doorcount++] = { x, y, dir };
            else
                doorcount++;
        }
    };

    for (int x = 0; x < board.width; x++)
    {
        process_edge(x, 0, Up);
        process_edge(x, board.height - 1, Down);
    }
    for (int y = 0; y < board.height; y++)
    {
        process_edge(0, y, Left);
        process_edge(board.width - 1, y, Right);
    }

    if (linecount > 2 || linecount + doorcount < 2)
        return SolveInvalid;

    bool didSomething = false;
    if (linecount >= 1 && !board.half_finished)
    {
        didSomething = true;
        board.half_finished = true;
        board.half_finish_point = linePos[0];
    }

    if (linecount == 2 && !board.finished)
    {
        didSomething = true;
        board.finished = true;
        board.finish_point = linePos[1];
    }

    if (doorcount > 0 && doorcount + linecount <= 2)
    {
        for (int i = 0; i < doorcount; i++)
        {
            board.set_edge(doors[i].x, doors[i].y, doors[i].dir, Board::EdgeLine);
        }
        didSomething = true;
    }

    return didSomething ? SolveChanged : SolveUnchanged;
}

SolveResult is_solved(Board& board)
{
    if (!board.half_finished || !board.finished)
        return ResultIndeterminate;

    int neededLength = board.width * board.height;

    int length;
    Point hfp = board.half_finish_point;
    Point out;
    if (!follow_line_on_edge(board, hfp.x, hfp.y, &out, &length))
        return ResultInvalid;

    if (out != board.finish_point)
        return ResultIndeterminate;

    if (length != neededLength)
        return ResultInvalid;

    return ResultSolved;
}

const char *wallChars =
// 00, 0U, D0, UD
"\x20\xBA\xBA\xBA" // 00
"\xCD\xBC\xBB\xB9" // 0L
"\xCD\xC8\xC9\xCC" // R0
"\xCD\xCA\xCB\xCE" // RL
;

const char *lineChars =
// 00, 0U, D0, UD
"\x2E\x2E\x2E\xB3" // 00
"\x2E\xD9\xBF\xB4" // 0L
"\x2E\xC0\xDA\xC3" // R0
"\xC4\xC1\xC2\xC5" // RL
;

const char *horizontalEdgeChars =
// Empty, wall, line, door
"\x20\xCD\xB3\x20"
;
const char *verticalEdgeChars =
// Empty, wall, line, door
"\x20\xBA\xC4\x20"
;

void draw_board(Board& board)
{
    for (int y = 0; y < board.height + 1; y++)
    {
        for (int x = 0; x < board.width + 1; x++)
        {
            int wallmask = 0;
            int wedge = Board::EdgeWall | Board::EdgeDoor;
            int hedge = Board::EdgeWall | Board::EdgeDoor;

            if (x == 0 || x == board.width)
                wedge |= Board::EdgeLine;
            if (y == 0 || y == board.height)
                hedge |= Board::EdgeLine;


            wallmask |= y > 0 && board.get_edge(x, y - 1, Left) & wedge ? 1 : 0;
            wallmask |= y < board.height && board.get_edge(x, y, Left) & wedge ? 2 : 0;
            wallmask |= x > 0 && board.get_edge(x - 1, y, Up) & hedge ? 4 : 0;
            wallmask |= x < board.width && board.get_edge(x, y, Up) & hedge ? 8 : 0;

            putchar(wallChars[wallmask]);

            if (x < board.width)
                putchar(horizontalEdgeChars[board.get_edge(x, y, Up)]);
        }

        putchar('\n');

        if (y < board.height)
        {
            for (int x = 0; x < board.width + 1; x++)
            {
                putchar(verticalEdgeChars[board.get_edge(x, y, Left)]);

                if (x < board.width)
                {
                    int linemask = 0;
                    int edge = Board::EdgeLine;

                    linemask |= board.get_edge(x, y, Up) & edge ? 1 : 0;
                    linemask |= board.get_edge(x, y, Down) & edge ? 2 : 0;
                    linemask |= board.get_edge(x, y, Left) & edge ? 4 : 0;
                    linemask |= board.get_edge(x, y, Right) & edge ? 8 : 0;

                    putchar(lineChars[linemask]);
                }
            }

            putchar('\n');
        }
    }
}

SolveResult deterministic_solve_board(Board& board)
{
    int state;
    do
    {
        state = SolveUnchanged;

        state |= solve_blocked_exits(board);
        state |= solve_two_freedoms(board);
        state |= solve_one_freedom(board);
        state |= solve_bouncing(board);

        if (state & SolveInvalid)
            return ResultInvalid;
    }
    while (state & SolveChanged);

    return is_solved(board);
}

SolveResult single_option_solve_board(Board& board)
{
    struct CellLine
    {
        Direction a, b;
    };

    static const CellLine cellLines[] = {
        { Up, Down },
        { Left, Right },
        { Up, Left },
        { Up, Right },
        { Down, Left },
        { Down, Right },
    };

    bool didSomething;
    do
    {
        didSomething = false;
        for (int y = 0; y < board.height; y++)
        {
            for (int x = 0; x < board.width; x++)
            {
                Board::CellState cell = board.get_cell(x, y);

                if (cell == Board::CellEmpty)
                {
                    int possible = 0;
                    int lastSolve = -1;
                    for (int i = 0; i < 6; i++)
                    {
                        CellLine lineType = cellLines[i];
                        if (board.get_edge(x, y, lineType.a) == Board::EdgeWall || board.get_edge(x, y, lineType.b) == Board::EdgeWall)
                            continue;

                        if (board.get_neighbor_cell(x, y, lineType.a) == Board::CellFullLine || board.get_edge(x, y, lineType.b) == Board::CellFullLine)
                            continue;

                        Board copy = board;
                        copy.set_edge(x, y, lineType.a, board.EdgeLine);
                        copy.set_edge(x, y, lineType.b, board.EdgeLine);
                        SolveResult result = deterministic_solve_board(copy);

                        if (result == ResultInvalid)
                            continue;
                        else if (result == ResultSolved)
                        {
                            board = copy;
                            return ResultSolved;
                        }
                        else if (result == ResultIndeterminate)
                        {
                            possible++;
                            lastSolve = i;
                        }
                    }
                    if (possible == 0)
                        return ResultInvalid;

                    if (possible == 1)
                    {
                        CellLine lineType = cellLines[lastSolve];
                        board.set_edge(x, y, lineType.a, board.EdgeLine);
                        board.set_edge(x, y, lineType.b, board.EdgeLine);
                        SolveResult result = deterministic_solve_board(board);
                        assert(result == ResultIndeterminate);
                        didSomething = true;
                    }
                }
            }
        }
    }
    while (didSomething);

    return ResultIndeterminate;
}

void load_board(Board& board, const char *file)
{
    int w, h, comp;
    stbi_uc *data = stbi_load(file, &w, &h, &comp, 0);

    auto get_data = [&](int x, int y, Direction dir)
    {
        Point p = get_offset(x * 2 + 1, y* 2 + 1, dir);
        return data[(p.x + p.y * w) * comp] < 50;
    };

    board.width = (w - 1) / 2;
    board.height = (h - 1) / 2;

    board.cell_states.resize(board.width * board.height, Board::CellEmpty);
    board.horizontal_edges.resize(board.width * (board.height + 1), Board::EdgeEmpty);
    board.vertical_edges.resize((board.width + 1) * board.height, Board::EdgeEmpty);

    for (int y = 0; y < board.height; y++)
    {
        board.set_edge(0, y, Left, Board::EdgeDoor);
        board.set_edge(board.width - 1, y, Right, Board::EdgeDoor);
    }
    for (int x = 0; x < board.width; x++)
    {
        board.set_edge(x, 0, Up, Board::EdgeDoor);
        board.set_edge(x, board.height - 1, Down, Board::EdgeDoor);
    }

    for (int y = 0; y < board.height; y++)
    {
        for (int x = 0; x < board.width; x++)
        {
            for (int i = 0; i < 4; i++)
            {
                if (get_data(x, y, (Direction)i))
                {
                    board.set_edge(x, y, (Direction)i, Board::EdgeWall);
                }
            }
        }
    }

    stbi_image_free(data);
}

int main(int argc, char** argv)
{
    Board board;

    load_board(board, "map11.bmp");

    draw_board(board);

    printf("Deterministic\n");

    auto before_det = std::chrono::high_resolution_clock::now();
    deterministic_solve_board(board);
    auto after_det = std::chrono::high_resolution_clock::now();

    draw_board(board);

    printf("Single option\n");

    auto before_opt = std::chrono::high_resolution_clock::now();
    SolveResult res = single_option_solve_board(board);
    auto after_opt = std::chrono::high_resolution_clock::now();

    draw_board(board);

    printf("Deterministic solve: %.1f ms\n", std::chrono::duration_cast<std::chrono::microseconds>(after_det - before_det).count() / 1000.0);
    printf("Single option solve: %.1f ms\n", std::chrono::duration_cast<std::chrono::microseconds>(after_opt - before_opt).count() / 1000.0);

    getchar();
}