#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <conio.h>
#include <windows.h>
#include <random>

using namespace std;

const int BOARD_SIZE = 4;
const int TARGET_NUMBER = 2048;

enum Direction { UP, DOWN, LEFT, RIGHT };

class Game2048 {
private:
    vector<vector<int>> board;
    int score;
    bool gameOver;
    bool win;

public:
    Game2048() : board(BOARD_SIZE, vector<int>(BOARD_SIZE, 0)), score(0), gameOver(false), win(false) {
        srand(time(nullptr));
        addRandomTile();
        addRandomTile();
    }

    void addRandomTile() {
        vector<pair<int, int>> emptyCells;
        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                if (board[i][j] == 0) {
                    emptyCells.push_back({i, j});
                }
            }
        }

        if (!emptyCells.empty()) {
            int randomIndex = rand() % emptyCells.size();
            int x = emptyCells[randomIndex].first;
            int y = emptyCells[randomIndex].second;
            board[x][y] = (rand() % 10 == 0) ? 4 : 2; // 90%概率生成2，10%概率生成4
        }
    }

    bool canMove(Direction dir) const {
        vector<vector<int>> tempBoard = board;
        return moveTiles(tempBoard, dir, false);
    }

    bool moveTiles(vector<vector<int>>& b, Direction dir, bool update = true) {
        bool moved = false;

        if (dir == UP || dir == DOWN) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                vector<int> column;
                for (int i = 0; i < BOARD_SIZE; ++i) {
                    if (dir == UP) {
                        if (b[i][j] != 0) column.push_back(b[i][j]);
                    } else {
                        if (b[BOARD_SIZE - 1 - i][j] != 0) column.push_back(b[BOARD_SIZE - 1 - i][j]);
                    }
                }

                vector<int> newColumn(BOARD_SIZE, 0);
                int index = 0;
                for (int i = 0; i < column.size(); ++i) {
                    if (i + 1 < column.size() && column[i] == column[i + 1]) {
                        newColumn[index] = column[i] * 2;
                        if (update) score += newColumn[index];
                        i++;
                    } else {
                        newColumn[index] = column[i];
                    }
                    index++;
                }

                for (int i = 0; i < BOARD_SIZE; ++i) {
                    if (dir == UP) {
                        if (b[i][j] != newColumn[i]) moved = true;
                        b[i][j] = newColumn[i];
                    } else {
                        if (b[BOARD_SIZE - 1 - i][j] != newColumn[i]) moved = true;
                        b[BOARD_SIZE - 1 - i][j] = newColumn[i];
                    }
                }
            }
        } else if (dir == LEFT || dir == RIGHT) {
            for (int i = 0; i < BOARD_SIZE; ++i) {
                vector<int> row;
                for (int j = 0; j < BOARD_SIZE; ++j) {
                    if (dir == LEFT) {
                        if (b[i][j] != 0) row.push_back(b[i][j]);
                    } else {
                        if (b[i][BOARD_SIZE - 1 - j] != 0) row.push_back(b[i][BOARD_SIZE - 1 - j]);
                    }
                }

                vector<int> newRow(BOARD_SIZE, 0);
                int index = 0;
                for (int j = 0; j < row.size(); ++j) {
                    if (j + 1 < row.size() && row[j] == row[j + 1]) {
                        newRow[index] = row[j] * 2;
                        if (update) score += newRow[index];
                        j++;
                    } else {
                        newRow[index] = row[j];
                    }
                    index++;
                }

                for (int j = 0; j < BOARD_SIZE; ++j) {
                    if (dir == LEFT) {
                        if (b[i][j] != newRow[j]) moved = true;
                        b[i][j] = newRow[j];
                    } else {
                        if (b[i][BOARD_SIZE - 1 - j] != newRow[j]) moved = true;
                        b[i][BOARD_SIZE - 1 - j] = newRow[j];
                    }
                }
            }
        }

        return moved;
    }

    void move(Direction dir) {
        if (canMove(dir)) {
            moveTiles(board, dir);
            addRandomTile();
            checkGameState();
        }
    }

    void checkGameState() {
        win = false;
        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                if (board[i][j] >= TARGET_NUMBER) {
                    win = true;
                    return;
                }
            }
        }

        bool hasEmpty = false;
        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE; ++j) {
                if (board[i][j] == 0) {
                    hasEmpty = true;
                    break;
                }
            }
            if (hasEmpty) break;
        }

        if (hasEmpty) {
            gameOver = false;
            return;
        }

        for (int i = 0; i < BOARD_SIZE; ++i) {
            for (int j = 0; j < BOARD_SIZE - 1; ++j) {
                if (board[i][j] == board[i][j + 1]) {
                    gameOver = false;
                    return;
                }
            }
        }

        for (int j = 0; j < BOARD_SIZE; ++j) {
            for (int i = 0; i < BOARD_SIZE - 1; ++i) {
                if (board[i][j] == board[i + 1][j]) {
                    gameOver = false;
                    return;
                }
            }
        }

        gameOver = true;
    }

    void printBoard() const {
        system("cls");
        cout << "\n\n2048 Game\n\n";
        cout << "Score: " << score << "\n\n";

        for (int i = 0; i < BOARD_SIZE; ++i) {
            cout << "+------+------+------+------+\n";
            cout << "|";
            for (int j = 0; j < BOARD_SIZE; ++j) {
                if (board[i][j] == 0) {
                    cout << "      |";
                } else {
                    cout << " " << board[i][j];
                    cout << string(5 - to_string(board[i][j]).length(), ' ') << "|";
                }
            }
            cout << "\n";
        }
        cout << "+------+------+------+------+\n\n";

        cout << "Controls:\n";
        cout << "W/↑: Up    S/↓: Down\n";
        cout << "A/←: Left  D/→: Right\n";
        cout << "Q: Quit\n\n";

        if (win) {
            cout << "Congratulations! You won!\n\n";
        } else if (gameOver) {
            cout << "Game Over! No more moves available.\n\n";
        }
    }

    bool isGameOver() const {
        return gameOver;
    }

    bool hasWon() const {
        return win;
    }

    int getScore() const {
        return score;
    }
};

int main() {
    Game2048 game;
    game.printBoard();

    while (!game.isGameOver() && !game.hasWon()) {
        char key = _getch();
        Direction dir;

        switch (key) {
            case 'w':
            case 'W':
            case 72: // 上箭头
                dir = UP;
                break;
            case 's':
            case 'S':
            case 80: // 下箭头
                dir = DOWN;
                break;
            case 'a':
            case 'A':
            case 75: // 左箭头
                dir = LEFT;
                break;
            case 'd':
            case 'D':
            case 77: // 右箭头
                dir = RIGHT;
                break;
            case 'q':
            case 'Q':
                cout << "Game aborted. Final score: " << game.getScore() << endl;
                return 0;
            default:
                continue;
        }

        game.move(dir);
        game.printBoard();
    }

    return 0;
}