ZeroJudge 解題筆記：c139. 00291 - The House Of Santa Claus

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


ZeroJudge 題目連結：c139. 00291 - The House Of Santa Claus

解題想法

先用一個陣列儲存每個節點可以連接的節點編號，再寫一個自訂函式，用遞迴及回溯跑所有可能的畫法。

Python 程式碼

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

def solve():
    import sys
    ans = []
    graph = [[], [2, 3, 5], [1, 3, 5],
             [1, 2, 4, 5], [3, 5], [1, 2, 3, 4]]
    def backtrack(u, path, visited):
        if len(path) == 9:
            ans.append(path)
            return
        for v in graph[u]:
            if (u, v) in visited or (v, u) in visited: continue
            visited.add((u, v))
            visited.add((v, u))
            backtrack(v, path + [v], visited)
            visited.remove((u, v))
            visited.remove((v, u))
    backtrack(1, [1], set())
    result = ["".join(map(str, a)) + "\n" for a in ans]
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

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

void backtrack(int u, vector<int>& path, set<vector<int>>& visited) {
    vector<vector<int>> graph = {{}, {2, 3, 5}, {1, 3, 5},
                                 {1, 2, 4, 5}, {3, 5}, {1, 2, 3, 4}};
    if (path.size() == 9) {
        for(int i=0; i<8; i++) printf("%d", path[i]);
        printf("%d\n", path[8]);
        return;
    }
    for(int v : graph[u]) {
        if (visited.count({u, v}) == 1 || visited.count({v, u}) == 1) continue;
        visited.insert({u, v});
        visited.insert({v, u});
        vector<int> tmp (path.begin(), path.end());
        tmp.push_back(v);
        backtrack(v, tmp, visited);
        visited.erase({u, v});
        visited.erase({v, u});
    }
}

int main() {
    vector<int> path = {1};
    set<vector<int>> visited;
    backtrack(1, path, visited);
    return 0;
}