#include <iostream>
#include <windows.h>
#include <conio.h>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int ROW = 13;
const int COL = 13;
const int BOX_NUM = 3;

void GotoXY(int x, int y)
{
    COORD coord;
    coord.X = x;
    coord.Y = y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}

void HideCursor()
{
    CONSOLE_CURSOR_INFO c;
    c.dwSize = 1;
    c.bVisible = FALSE;
    SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &c);
}

char map[ROW][COL];
int px, py;
int dir4[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

void FindPlayer();
bool IsReachable(int sx, int sy, int ex, int ey, char tmpMap[ROW][COL]);
void CopyMap(char src[ROW][COL], char dst[ROW][COL]);
void GenerateMap();

bool IsReachable(int sx, int sy, int ex, int ey, char tmpMap[ROW][COL])
{
    bool vis[ROW][COL] = {false};
    queue<pair<int, int>> q;
    q.push(make_pair(sx, sy));
    vis[sy][sx] = true;

    while(!q.empty())
    {
        pair<int,int> cur = q.front();
        q.pop();
        int x = cur.first;
        int y = cur.second;

        if(x == ex && y == ey)
            return true;

        for(int d = 0; d < 4; d++)
        {
            int nx = x + dir4[d][0];
            int ny = y + dir4[d][1];

            if(nx > 0 && nx < COL - 1 && ny > 0 && ny < ROW - 1)
            {
                if(!vis[ny][nx] && tmpMap[ny][nx] != '#')
                {
                    vis[ny][nx] = true;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
    return false;
}

void CopyMap(char src[ROW][COL], char dst[ROW][COL])
{
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++)
            dst[i][j] = src[i][j];
}

void FindPlayer()
{
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++)
            if(map[i][j] == '@')
            {
                py = i;
                px = j;
                return;
            }
}

void DrawMap()
{
    GotoXY(0, 0);
    for(int i = 0; i < ROW; i++)
    {
        for(int j = 0; j < COL; j++)
            cout << map[i][j];
        cout << endl;
    }
    cout << "WASD移动 | R重新生成 | Q退出";
}

bool CheckWin()
{
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++)
            if(map[i][j] == '$')
                return false;
    return true;
}

void Move(int dx, int dy)
{
    int nx = px + dx;
    int ny = py + dy;

    if(map[ny][nx] == '#')
        return;

    if(map[ny][nx] == ' ' || map[ny][nx] == '.')
    {
        if(map[py][px] == '+')
            map[py][px] = '.';
        else
            map[py][px] = ' ';

        if(map[ny][nx] == '.')
            map[ny][nx] = '+';
        else
            map[ny][nx] = '@';

        px = nx;
        py = ny;
        return;
    }

    if(map[ny][nx] == '$' || map[ny][nx] == '*')
    {
        int boxNextX = nx + dx;
        int boxNextY = ny + dy;

        if(map[boxNextY][boxNextX] == '#' ||
           map[boxNextY][boxNextX] == '$' ||
           map[boxNextY][boxNextX] == '*')
            return;

        if(map[boxNextY][boxNextX] == '.')
            map[boxNextY][boxNextX] = '*';
        else
            map[boxNextY][boxNextX] = '$';

        if(map[py][px] == '+')
            map[py][px] = '.';
        else
            map[py][px] = ' ';

        if(map[ny][nx] == '*')
            map[ny][nx] = '+';
        else
            map[ny][nx] = '@';

        px = nx;
        py = ny;
    }
}

// 关键：生成一个中心连通的大房间，不再乱撒墙
void GenerateMap()
{
    while(true)
    {
        char temp[ROW][COL];

        for(int i = 0; i < ROW; i++)
            for(int j = 0; j < COL; j++)
                temp[i][j] = ' ';

        for(int i = 0; i < ROW; i++)
        {
            temp[i][0] = '#';
            temp[i][COL - 1] = '#';
        }
        for(int j = 0; j < COL; j++)
        {
            temp[0][j] = '#';
            temp[ROW - 1][j] = '#';
        }

        // 只在边缘放少量内墙，中心保持可推空间
        for(int i = 1; i < ROW - 1; i++)
        {
            for(int j = 1; j < COL - 1; j++)
            {
                if(abs(i - ROW / 2) <= 2 && abs(j - COL / 2) <= 2)
                    continue;

                int r = rand() % 100;
                if(r < 12)
                    temp[i][j] = '#';
            }
        }

        int pX = COL / 2;
        int pY = ROW / 2;
        temp[pY][pX] = '@';

        vector<pair<int,int>> boxes;
        vector<pair<int,int>> targets;

        int cnt = 0;
        while(cnt < BOX_NUM)
        {
            int x = rand() % (COL - 4) + 2;
            int y = rand() % (ROW - 4) + 2;

            if(temp[y][x] == ' ' && IsReachable(pX, pY, x, y, temp))
            {
                temp[y][x] = '$';
                boxes.push_back(make_pair(x, y));
                cnt++;
            }
        }

        cnt = 0;
        while(cnt < BOX_NUM)
        {
            int x = rand() % (COL - 4) + 2;
            int y = rand() % (ROW - 4) + 2;

            if(temp[y][x] == ' ')
            {
                temp[y][x] = '.';
                targets.push_back(make_pair(x, y));
                cnt++;
            }
        }

        bool allOk = true;

        for(int b = 0; b < boxes.size(); b++)
        {
            int bx = boxes[b].first;
            int by = boxes[b].second;

            bool canPushToTarget = false;

            for(int t = 0; t < targets.size(); t++)
            {
                int tx = targets[t].first;
                int ty = targets[t].second;

                if(IsReachable(bx, by, tx, ty, temp))
                {
                    canPushToTarget = true;
                    break;
                }
            }

            if(!canPushToTarget)
            {
                allOk = false;
                break;
            }
        }

        if(allOk)
        {
            CopyMap(temp, map);
            break;
        }
    }

    FindPlayer();
}

int main()
{
    HideCursor();
    srand((unsigned)time(NULL));
    GenerateMap();

    char key;

    while(true)
    {
        DrawMap();

        if(CheckWin())
        {
            GotoXY(0, ROW + 2);
            cout << "==== 恭喜通关！按R刷新 ====" << endl;
        }

        if(_kbhit())
        {
            key = _getch();
            switch(key)
            {
                case 'w': Move(0, -1); break;
                case 's': Move(0, 1); break;
                case 'a': Move(-1, 0); break;
                case 'd': Move(1, 0); break;
                case 'r': GenerateMap(); break;
                case 'q': return 0;
            }
        }

        Sleep(40);
    }

    system("pause");
    return 0;
}