ZeroJudge 解題筆記：c133. 00639 - Don't Get Rooked

作者：王一哲
日期：2026年3月24日


ZeroJudge 題目連結：c133. 00639 - Don't Get Rooked

解題想法

這題很像八皇后，用集合 rooks 儲存已經放置城堡的位置，寫一個自訂函式 is_safe 檢查代入的位置 (row, col) 是否安全；再寫另一個自訂函式 backtrack 代入 (0, 0)，用遞迴與回溯找答案。

Python 程式碼

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

import sys

def solve(n):
    grid = [list(sys.stdin.readline().strip()) for _ in range(n)]
    rooks = set()  # 已放置城堡的位置
    ans = 0  # 答案
    """ grid[row][col] 處是否可以放置城堡 """
    def is_safe(row, col):
        for r in range(row-1, -1, -1):  # 向上檢查
            if grid[r][col] == 'X': break
            if (r, col) in rooks: return False
        for r in range(row+1, n, 1):  # 向下檢查
            if grid[r][col] == 'X': break
            if (r, col) in rooks: return False
        for c in range(col-1, -1, -1):  # 向左檢查
            if grid[row][c] == 'X': break
            if (row, c) in rooks: return False
        for c in range(col+1, n, 1):  # 向右檢查
            if grid[row][c] == 'X': break
            if (row, c) in rooks: return False
        return True  # 通過 4 個方向的檢查，回傳 True
    """ 回溯，代入 row, col """
    def backtrack(row, col):
        nonlocal ans  # 這樣才能修改函數外的變數值
        if col == n:  # 如果欄已經出界
            col = 0   # 歸零
            row += 1  # 找下一列
        if row == n:  # 如果列已經出界
            ans = max(ans, len(rooks))  # 更新答案
            return    # 遞迴出口
        # 測試 (row, col) 是否可以放置城堡
        if grid[row][col] == '.' and is_safe(row, col):
            rooks.add((row, col))  # 放置城堡
            backtrack(row, col+1)  # 遞迴，測試下一欄是否能放置城堡
            rooks.remove((row, col))  # 回溯
        backtrack(row, col+1)  # 遞迴，不在 (row, col) 處放置城堡
    """ End of backtrack """
    backtrack(0, 0)  # 從 (0, 0) 開始測試
    return ans

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    result.append(f"{solve(n):d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;

int n, ans;
vector<string> grid (10);
set<pair<int, int>> rooks;

bool is_safe(int row, int col) {
    for(int r=row-1; r>=0; r--) {
        if (grid[r][col] == 'X') break;
        if (rooks.count(make_pair(r, col)) == 1) return false;
    }
    for(int r=row+1; r<n; r++) {
        if (grid[r][col] == 'X') break;
        if (rooks.count(make_pair(r, col)) == 1) return false;
    }
    for(int c=col-1; c>=0; c--) {
        if (grid[row][c] == 'X') break;
        if (rooks.count(make_pair(row, c)) == 1) return false;
    }
    for(int c=col+1; c<n; c++) {
        if (grid[row][c] == 'X') break;
        if (rooks.count(make_pair(row, c)) == 1) return false;
    }
    return true;
}

void backtrack(int row, int col) {
    if (col == n) {
        col = 0; row++;
    }
    if (row == n) {
        ans = max(ans, (int)rooks.size());
        return;
    }
    if (grid[row][col] == '.' && is_safe(row, col)) {
        rooks.insert(make_pair(row, col));
        backtrack(row, col+1);
        rooks.erase(make_pair(row, col));
    }
    backtrack(row, col+1);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> n && n != 0) {
        grid.resize(n);
        ans = 0;
        rooks.clear();
        for(int i=0; i<n; i++) cin >> grid[i];
        backtrack(0, 0);
        cout << ans << "\n";
    }
    return 0;
}