ZeroJudge 解題筆記：f822. 紅林愛下棋

作者：王一哲
日期：2025年10月26日


ZeroJudge 題目連結：f822. 紅林愛下棋

解題想法

這題分成兩個部分。首先依序掃過每一格，如果這格是 .，用 list 儲存待走訪佇列，假設目前區塊的顏色 color 為 X，用四方位檢查找周圍的格子 (nr, nc)，如果 (nr, nc) 是 B 或 W，設定 color 的值； 如果 color 已經是 B 或 W，但是 (nr, nc) 的顔色與 color 不同，錯誤，無法計算領地大小。找到連通區塊之後，將 que 裡的格子改成 color 的值。第二部分，再用二層 for 迴圈，計算黑、白棋數量。最後按照題目的要求輸出答案。

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

def solve():
    grid = [list(input()) + ["#"] for _ in range(9)]  # 地圖，在最右側、最下方加 # 作為哨兵
    grid.append(["#"]*10)
    for i in range(9):  # 依序掃過每一格
        for j in range(9):
            if grid[i][j] == ".":  # 如果此格是 .
                que = [(i, j)]  # 將 (i, j) 加到待走訪佇列 que
                head = 0  # 從 que 讀取資料的索引值
                color = "X"  # 目前區塊的顏色，預設為 X
                ### BFS ###
                while head < len(que):  # 如果 head 還沒有出界繼續執行
                    r, c = que[head]; head += 1  # 從 que 讀取待走訪位置，head 加 1
                    for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方向檢查
                        nr, nc = r+dr, c+dc  # 要檢查 (nr, nc)
                        if grid[nr][nc] == "#": continue  # 如果此格是邊界，找下一格
                        if (color == "B" and grid[nr][nc] == "W") or \  # 區塊顏色 B、此格顏色 W
                           (color == "W" and grid[nr][nc] == "B"):      # 區塊顏色 W、此格顏色 B
                                print("Wrong"); return  # 錯誤，離開函式
                        elif (color == "B" or color == "W") and grid[nr][nc] == ".":  # 區塊為 B 或 W，此格為 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                        elif color == "X":  # 如果區塊還沒有決定顏色
                            if grid[nr][nc] == ".":  # 如果此格是 .
                                grid[nr][nc] = "@"  # 暫時填入 @，避免重複走訪
                                que.append((nr, nc))  # (nr, nc) 加入 que
                            elif grid[nr][nc] == "B" or grid[nr][nc] == "W":  # 如果此格是 B 或 W
                                color = grid[nr][nc]  # 更新區塊顏色
                ### End of BFS ###
                for r, c in que: grid[r][c] = color  # 將 que 之中的位置填入對應的顏色
    ### 已掃過所有格子，計算黑、白棋數量 ###
    B, W = 0, 0  # 黑、白棋數量
    for i in range(9):
        for j in range(9):
            if grid[i][j] == "B": B += 1
            elif grid[i][j] == "W": W += 1
    ### 印出題目要求的答案 ###
    print("Black wins!!" if B > W else "White wins!!")
    print(f"{B:d}:{W:d}")
    for row in grid[:9]: print("".join(row[:9]))
### 主程式 ###
if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 2 ms，記憶體約為 276 kB，通過測試。

#include <cstdio>
#include <vector>
#include <utility>
using namespace std;

void solve() {
    vector<vector<char>> grid (11, vector<char> (11, '#'));  // 地圖，四周加一圈 # 作為哨兵
    for(int i=1; i<=9; i++) {  // 讀取地圖
        scanf("%s", &grid[i][1]);
        grid[i][10] = '#';
    }
    for(int i=1; i<=9; i++) {  // 依序掃過每一格
        for(int j=1; j<=9; j++) {
            if (grid[i][j] == '.') {  // 如果此格是 .
                vector<pair<int, int>> que = {{i, j}};  // 將 (i, j) 加到待走訪佇列 que
                int head = 0;  // 從 que 讀取資料的索引值
                char color = 'X';  // 目前區塊的顏色，預設為 X
                /* BFS */
                int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
                while(head < (int)que.size()) {  // 如果 head 還沒有出界繼續執行
                    int r = que[head].first, c = que[head].second; head++;  // 從 que 讀取待走訪位置，head 加 1
                    for(int k=0; k<4; k++) {  // 四方向檢查
                        int nr = r+dr[k], nc = c+dc[k];  // 要檢查 (nr, nc)
                        if (grid[nr][nc] == '#') continue;  // 如果此格是邊界，找下一格
                        // 區塊顏色 B、此格顏色 W，區塊顏色 W、此格顏色 B
                        if ((color == 'B' && grid[nr][nc] == 'W') || (color == 'W' && grid[nr][nc] == 'B')) {
                                printf("Wrong\n"); return;  // 錯誤，離開函式
                        } else if ((color == 'B' || color == 'W') && grid[nr][nc] == '.') {  // 區塊為 B 或 W，此格為 .
                                grid[nr][nc] = '@';  // 暫時填入 @，避免重複走訪
                                que.push_back(make_pair(nr, nc));  // (nr, nc) 加入 que
                        } else if (color == 'X') {  // 如果區塊還沒有決定顏色
                            if (grid[nr][nc] == '.') {  // 如果此格是 .
                                grid[nr][nc] = '@';  // 暫時填入 @，避免重複走訪
                                que.push_back(make_pair(nr, nc));  // (nr, nc) 加入 que
                            } else if (grid[nr][nc] == 'B' || grid[nr][nc] == 'W') {  // 如果此格是 B 或 W
                                color = grid[nr][nc];  // 更新區塊顏色
                            }
                        }
                    }
                }
                /* End of BFS */
                for(auto it : que) grid[it.first][it.second] = color;  // 將 que 之中的位置填入對應的顏色
            }
        }
    }
    /* 已掃過所有格子，計算黑、白棋數量 */
    int B = 0, W = 0;  // 黑、白棋數量
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) {
            if (grid[i][j] == 'B') B++;
            else if (grid[i][j] == 'W') W++;
        }
    }
    /* 印出題目要求的答案 */
    if (B > W) printf("Black wins!!\n");
    else printf("White wins!!\n");
    printf("%d:%d\n", B, W);
    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) {
            printf("%c", grid[i][j]);
        }
        puts("");
    }
}

int main() {
    solve();
    return 0;
}