alan23273850 的刷題筆記
c139: 00291 - The House Of Santa Claus
Tags: graph
出處：https://zerojudge.tw/ShowProblem?problemid=c139
提交：https://zerojudge.tw/Submissions?problemid=c139&account=allllllan123456
問題：給定一間小屋的一筆畫圖形，請求出能一筆畫出這間小屋的所有可能畫法，並且按照字典序印出。
解法：就 DFS，只是覺得一筆畫的問題很有趣於是收錄在這邊。如果能善用 C++ 資料結構的話寫出來的程式碼也是可以很漂亮的。
1#include <bits/stdc++.h>
2using namespace std;
3
4bool edges[8];
5int path[9], pathL = 0;
6vector<pair<int, int>> adj[6];
7
8void dfs(int id) {
9 path[pathL++] = id;
10 if (pathL == 9) {
11 for (int i=0; i<pathL; i++) cout << path[i];
12 cout << '\n';
13 } else
14 for (const auto &pii: adj[id]) {
15 if (!edges[pii.second]) {
16 edges[pii.second] = true;
17 dfs(pii.first);
18 edges[pii.second] = false;
19 }
20 }
21 pathL--;
22}
23
24int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
25 adj[1] = {{2,0}, {3,5}, {5,4}};
26 adj[2] = {{1,0}, {3,1}, {5,7}};
27 adj[3] = {{1,5}, {2,1}, {4,2}, {5,6}};
28 adj[4] = {{3,2}, {5,3}};
29 adj[5] = {{1,4}, {2,7}, {3,6}, {4,3}};
30 dfs(1);
31 return 0;
32}