ZeroJudge 解題筆記：c104. 00167 - The Sultan's Successors

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


ZeroJudge 題目連結：c104. 00167 - The Sultan's Successors

解題想法

八皇后的變型，主要考遞迴跟回溯。

Python 程式碼

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

import sys

def solve(grid):  # 主要的解題函式
    rows = [-1]*8  # 目前皇后放置的列
    cols, dia1, dia2 = set(), set(), set()  # 已用的欄、左上右下對角線、右上左下對角線
    imax = 0  # 最高分，預設為 0
    ### 回溯，代入列、目前的分數 ###
    def backtrack(row, curr):
        nonlocal imax  # 這樣才能改變外層 imax 的值
        if row == 8:  # 遞迴出口，已放置 8 個皇后
            imax = max(imax, curr)  # 更新 imax
        # 試著在此列每一欄放置皇后
        for col in range(8):
            # 檢查欄、左上右下、右上左下是否已被佔用
            if col not in cols and (row-col) not in dia1 and (row+col) not in dia2:
                # 可以放置皇后
                rows[row] = col
                cols.add(col)
                dia1.add(row-col)
                dia2.add(row+col)
                # 遞迴到下一列，代入加上 (row, col) 的分數
                backtrack(row+1, curr+grid[row][col])
                # 回溯，移除皇后，恢復佔用的狀態
                rows[row] = -1
                cols.remove(col)
                dia1.remove(row-col)
                dia2.remove(row+col)
    ### End of backtrack ###
    backtrack(0, 0)  # 從第 0 列、分數 0 開始回溯
    return imax  # 回傳最高分

idx = 0
lines = sys.stdin.readlines()
t = int(lines[idx])
idx += 1
for _ in range(t):
    grid = [list(map(int, line.split())) for line in lines[idx:idx+8]]
    idx += 8
    imax = solve(grid)
    sys.stdout.write(f"{imax:5d}\n")

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<vector<int>> grid;  // 地圖
vector<int> rows;  // 已用的列
set<int> cols, dia1, dia2;  // 已用的欄、左上右下對角線、右上左下對角線
int imax;  // 最高分

/* 回溯，代入目前的列、分數 */
int backtrack(int row, int curr) {
    if (row == 8) {  // 遞迴出口，已放置 8 個皇后
        imax = max(imax, curr);  // 更新 imax
        return imax;  // 回傳 imax
    }
    for(int col=0; col<8; col++) {  // 試著在此列每一欄放置皇后
        // 檢查欄、左上右下、右上左下是否已被佔用
        if (cols.count(col) == 0 && dia1.count(row-col) == 0 && dia2.count(row+col) == 0) {
            // 可以放置皇后
            rows[row] = col;
            cols.insert(col);
            dia1.insert(row-col);
            dia2.insert(row+col);
            // 遞迴到下一列，代入加上 (row, col) 的分數
            imax = backtrack(row+1, curr+grid[row][col]);
            // 回溯，移除皇后，恢復佔用的狀態
            rows[row] = -1;
            cols.erase(col);
            dia1.erase(row-col);
            dia2.erase(row+col);
        }
    }
    return imax;  // 回傳 imax
}

/* 主要的解題函式 */
int solve() {
    rows.assign(8, -1);  // 重置目前皇后放置的列
    // 清空已用的欄、左上右下對角線、右上左下對角線
    cols.clear(); dia1.clear(); dia2.clear();
    imax = 0;  // 重置最高分
    return backtrack(0, 0);  // 呼叫 backtrack 求最高分
}

int main() {
    int T; scanf("%d", &T);  // T 組測資
    for(int t=0; t<T; t++) {
        grid.resize(8);  // 重置地圖
        for(int r=0; r<8; r++) {
            grid[r].resize(8);
            for(int c=0; c<8; c++) {
                scanf("%d", &grid[r][c]);
            }
        }
        imax = solve();  // 最高分
        printf("%5d\n", imax);  // 輸出寬度為 5 格
    }
    return 0;
}