#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <algorithm>
using namespace std;

const int BOARD_SIZE = 11;

enum Piece {
    EMPTY = 0,
    BLACK = 1,
    WHITE = 2
};

enum GameMode {
    PVP = 1,
    PVE = 2
};

class GomokuGame {
private:
    vector<vector<Piece>> board;
    Piece currentPlayer;
    GameMode mode;
    bool gameOver;
    Piece winner;
    
public:
    GomokuGame() : currentPlayer(BLACK), gameOver(false), winner(EMPTY) {
        initializeBoard();
    }
    
    void initializeBoard() {
        board.clear();
        for (int i = 0; i < BOARD_SIZE; i++) {
            vector<Piece> row(BOARD_SIZE, EMPTY);
            board.push_back(row);
        }
    }
    
    void printBoard() {
        // 打印列号
        cout << "   ";
        for (int j = 0; j < BOARD_SIZE; j++) {
            cout << j << " ";
        }
        cout << endl;
        
        // 打印分隔线
        cout << "   ";
        for (int j = 0; j < BOARD_SIZE; j++) {
            cout << "--";
        }
        cout << endl;
        
        // 打印棋盘内容
        for (int i = 0; i < BOARD_SIZE; i++) {
            // 打印行号
            cout << i << " |";
            
            // 打印棋子
            for (int j = 0; j < BOARD_SIZE; j++) {
                switch (board[i][j]) {
                    case EMPTY: 
                        cout << ". ";  // 使用点号表示空位置
                        break;
                    case BLACK: cout << "X "; break;  // 使用小字符表示黑子
                    case WHITE: cout << "O "; break;  // 使用小字符表示白子
                }
            }
            cout << endl;
        }
        
        // 打印底部分隔线
        cout << "   ";
        for (int j = 0; j < BOARD_SIZE; j++) {
            cout << "--";
        }
        cout << endl;
    }
    
    bool isValidMove(int row, int col) {
        return row >= 0 && row < BOARD_SIZE && 
               col >= 0 && col < BOARD_SIZE && 
               board[row][col] == EMPTY;
    }
    
    bool makeMove(int row, int col) {
        if (!isValidMove(row, col)) {
            return false;
        }
        
        board[row][col] = currentPlayer;
        
        if (checkWin(row, col)) {
            gameOver = true;
            winner = currentPlayer;
            return true;
        }
        
        // 检查是否平局
        if (isBoardFull()) {
            gameOver = true;
            return true;
        }
        
        // 切换玩家
        currentPlayer = (currentPlayer == BLACK) ? WHITE : BLACK;
        return true;
    }
    
    bool checkWin(int row, int col) {
        Piece piece = board[row][col];
        if (piece == EMPTY) return false;
        
        // 检查方向: 水平、垂直、两条对角线
        int directions[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
        
        for (auto dir : directions) {
            int count = 1;  // 当前位置已经有一个棋子
            
            // 正向检查
            for (int i = 1; i < 5; i++) {
                int r = row + dir[0] * i;
                int c = col + dir[1] * i;
                
                if (r < 0 || r >= BOARD_SIZE || c < 0 || c >= BOARD_SIZE || board[r][c] != piece) {
                    break;
                }
                count++;
            }
            
            // 反向检查
            for (int i = 1; i < 5; i++) {
                int r = row - dir[0] * i;
                int c = col - dir[1] * i;
                
                if (r < 0 || r >= BOARD_SIZE || c < 0 || c >= BOARD_SIZE || board[r][c] != piece) {
                    break;
                }
                count++;
            }
            
            if (count >= 5) {
                return true;
            }
        }
        
        return false;
    }
    
    bool isBoardFull() {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                if (board[i][j] == EMPTY) {
                    return false;
                }
            }
        }
        return true;
    }
    
    void aiMove() {
        // 简单的AI策略：尝试在有利位置落子
        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] == EMPTY) {
                    emptyCells.push_back({i, j});
                }
            }
        }
        
        if (emptyCells.empty()) return;
        
        // 优先选择靠近已有棋子的位置
        vector<pair<int, int>> candidateMoves;
        
        for (auto cell : emptyCells) {
            int i = cell.first;
            int j = cell.second;
            
            // 检查周围是否有棋子
            for (int dx = -2; dx <= 2; dx++) {
                for (int dy = -2; dy <= 2; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    
                    int ni = i + dx;
                    int nj = j + dy;
                    
                    if (ni >= 0 && ni < BOARD_SIZE && nj >= 0 && nj < BOARD_SIZE) {
                        if (board[ni][nj] != EMPTY) {
                            candidateMoves.push_back({i, j});
                            break;
                        }
                    }
                }
            }
        }
        
        // 如果没有合适的候选位置，随机选择
        if (candidateMoves.empty()) {
            candidateMoves = emptyCells;
        }
        
        // 随机选择一个候选位置
        srand(time(0));
        int index = rand() % candidateMoves.size();
        int row = candidateMoves[index].first;
        int col = candidateMoves[index].second;
        
        cout << "AI落子位置: " << row << " " << col << endl;
        makeMove(row, col);
    }
    
    void startGame() {
        cout << "========== 五子棋游戏 ==========" << endl;
        cout << "请选择游戏模式:" << endl;
        cout << "1. 双人对战" << endl;
        cout << "2. 人机对战" << endl;
        cout << "请输入选择 (1 或 2): ";
        
        int choice;
        while (true) {
            cin >> choice;
            if (choice == 1 || choice == 2) {
                break;
            }
            cout << "输入无效，请重新输入 (1 或 2): ";
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
        }
        
        if (choice == 1) {
            mode = PVP;
            cout << "已选择双人对战模式" << endl;
            cout << "黑棋(X) 先行, 白棋(O) 后行" << endl;
        } else {
            mode = PVE;
            cout << "已选择人机对战模式" << endl;
            cout << "玩家(X) 先行, AI(O) 后行" << endl;
        }
        
        cout << "游戏开始!" << endl;
        cout << "坐标范围: 0-" << BOARD_SIZE-1 << endl;
        
        while (!gameOver) {
            printBoard();
            
            if (currentPlayer == BLACK) {
                cout << "黑棋(X)回合" << endl;
            } else {
                cout << "白棋(O)回合" << endl;
            }
            
            if (mode == PVE && currentPlayer == WHITE) {
                // AI回合
                cout << "AI思考中..." << endl;
                aiMove();
            } else {
                // 玩家回合
                int row, col;
                cout << "请输入落子位置 (行 列, 例如: 5 5): ";
                
                while (true) {
                    cin >> row >> col;
                    
                    if (cin.fail()) {
                        cin.clear();
                        cin.ignore(numeric_limits<streamsize>::max(), '\n');
                        cout << "输入无效，请重新输入: ";
                        continue;
                    }
                    
                    if (row < 0 || row >= BOARD_SIZE || col < 0 || col >= BOARD_SIZE) {
                        cout << "坐标超出范围，请重新输入 (0-" << BOARD_SIZE-1 << "): ";
                        continue;
                    }
                    
                    if (isValidMove(row, col)) {
                        if (makeMove(row, col)) {
                            break;
                        }
                    } else {
                        cout << "该位置已有棋子，请重新输入: ";
                    }
                }
            }
        }
        
        printBoard();
        if (winner != EMPTY) {
            cout << (winner == BLACK ? "黑棋(X)" : "白棋(O)") << "获胜!" << endl;
        } else {
            cout << "平局! 棋盘已满!" << endl;
        }
    }
};

int main() {
    char playAgain;
    
    do {
        GomokuGame game;
        game.startGame();
        
        cout << "是否再玩一局? (y/n): ";
        cin >> playAgain;
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        
    } while (playAgain == 'y' || playAgain == 'Y');
    
    cout << "谢谢游玩!" << endl;
    return 0;
}