您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

UVA 220 Othello（黑白棋）問題詳解與C++模擬實現

編輯：關於C語言

UVA 220 Othello（黑白棋）問題詳解與C++模擬實現

Othello（黑白棋）是雙人對戰棋類遊戲，在8×8棋盤上進行。雙方輪流落子，落子必須翻轉至少一枚對方棋子：被翻轉的棋子必須在同一直線（橫、豎、斜）上，且兩端分別為己方新落子與己方既有棋子。單步可同時翻轉多條方向的棋子。

輸入格式

第一行：測試用例數 T。
每個用例：
- 前8行：棋盤狀態，每行8字符。-空位，B黑棋，W白棋。
- 第9行：當前玩家（B或W）。
- 後續行：命令序列，每行一條，以Q結束該用例。
  - L：列出當前玩家所有合法落子位置，按行優先、列遞增序輸出(x,y)（1-based），無合法手輸出No legal move.。
  - Mxy：當前玩家在(x,y)落子。若無合法手，先切換玩家再落子（保證合法）。落子後輸出Black - xx White - yy，並切換玩家。
  - Q：結束用例，輸出最終棋盤（8行）。
用例間輸出空一行。

核心邏輯：合法落子判定與翻轉

對於空位(r,c)，沿8個方向(dr,dc)檢查：相鄰格必須為對方棋，沿該方向連續對方棋後遇到己方棋，則該方向可翻轉。若8方向至少一個可翻轉，則落子合法。

實際翻轉時，對每個可翻轉方向，將中間所有對方棋改為己方棋，最後在(r,c)放置己方棋。

C++ 參考實現（AC代碼）

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

char board[10][10];
int cntB, cntW;
bool exchangeFlag; // 標記M命令是否切換了玩家

void initializer() {
    cntB = cntW = 0;
    exchangeFlag = false;
    for (int i = 0; i < 8; ++i) cin >> board[i];
}

void solveCommand(char cmd[], char player) {
    if (cmd[0] == 'L') solveL(player);
    else if (cmd[0] == 'M') solveM(player, cmd[1]-'1', cmd[2]-'1');
    else if (cmd[0] == 'Q') solveQ();
}

void solveL(char player) {
    bool found = false;
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
            if (board[i][j] == '-' && checkPoint(player, i, j)) {
                if (found) cout << ' ';
                cout << '(' << i+1 << ',' << j+1 << ')';
                found = true;
            }
    if (!found) cout << "No legal move.";
    cout << endl;
}

void solveM(char player, int r, int c) {
    if (checkPoint(player, r, c)) {
        actPoint(player, r, c);
        exchangeFlag = true;
    } else {
        actPoint('B'+'W'-player, r, c); // 切換玩家落子
    }
    countPieces();
    cout << "Black -" << setw(3) << cntB << " White -" << setw(3) << cntW << endl;
}

void countPieces() {
    cntB = cntW = 0;
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j) {
            if (board[i][j] == 'B') ++cntB;
            else if (board[i][j] == 'W') ++cntW;
        }
}

void solveQ() {
    for (int i = 0; i < 8; ++i) cout << board[i] << endl;
}

// 檢查(player,r,c)是否合法：8方向任一可翻轉即合法
bool checkPoint(char player, int r, int c) {
    char opp = 'B'+'W'-player;
    for (int dr = -1; dr <= 1; ++dr)
        for (int dc = -1; dc <= 1; ++dc) {
            if (dr==0 && dc==0) continue;
            int nr = r+dr, nc = c+dc;
            if (nr<0 || nr>=8 || nc<0 || nc>=8 || board[nr][nc]!=opp) continue;
            // 繼續沿(dr,dc)尋找己方棋
            while (true) {
                nr += dr; nc += dc;
                if (nr<0 || nr>=8 || nc<0 || nc>=8) break;
                if (board[nr][nc] == '-') break;
                if (board[nr][nc] == player) return true; // 找到己方棋，合法
            }
        }
    return false;
}

// 執行落子並翻轉
void actPoint(char player, int r, int c) {
    char opp = 'B'+'W'-player;
    for (int dr = -1; dr <= 1; ++dr)
        for (int dc = -1; dc <= 1; ++dc) {
            if (dr==0 && dc==0) continue;
            int nr = r+dr, nc = c+dc;
            if (nr<0 || nr>=8 || nc<0 || nc>=8 || board[nr][nc]!=opp) continue;
            // 記錄可翻轉路徑
            vector> path;
            while (true) {
                if (nr<0 || nr>=8 || nc<0 || nc>=8) { path.clear(); break; }
                if (board[nr][nc] == '-') { path.clear(); break; }
                if (board[nr][nc] == player) break; // 找到己方棋，path有效
                path.emplace_back(nr, nc);
                nr += dr; nc += dc;
            }
            for (auto &p : path) board[p.first][p.second] = player;
        }
    board[r][c] = player;
}

int main() {
    int T; cin >> T;
    char cmd[10];
    for (int tc = 0; tc < T; ++tc) {
        if (tc) cout << endl;
        initializer();
        char player; cin >> player;
        while (cin >> cmd) {
            solveCommand(cmd, player);
            if (exchangeFlag) { player = 'B'+'W'-player; exchangeFlag = false; }
            if (cmd[0] == 'Q') break;
        }
    }
    return 0;
}