UVa 291
題目
http://domen111.github.io/UVa-Easy-Viewer/?291
如下圖所示，有編號 $1$~$5$ 的五個點，假設每一條邊都是雙向的
列出所有從 $1$ 開始每條邊最多只經過一次，並且每個點都有走到的情況，也就是一筆劃問題
想法
要枚舉有哪些情況，就必須要先知道每個點可以連接到哪些點
我們可以預處理一張表，紀錄 $a$ 到 $b$ 是否有邊連通
接下來要符合一條邊的情況，就必須記錄每條邊是否被走過
一樣的，可以用一個表格紀錄 $a$ 到 $b$ 之間的邊是否被走過
最後就從 $1$ 點開始對於每個可以走的點都走過一次，枚舉出所有情況即可
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<iostream>
using namespace std;
bool nxt[6][6];
int res[10], vis[6][6];
void DFS(int depth, int last){
if(depth == 9){
for(int i=0 ; i<9 ; i++){
cout<<res[i];
}
cout<<"\n";
return;
}
for(int i=1 ; i<=6 ; i++){
if(!vis[last][i] && !vis[i][last] && nxt[last][i]){
vis[last][i] = vis[i][last] = true;
res[depth] = i;
DFS(depth+1, i);
vis[last][i] = vis[i][last] = false;
}
}
}
int main(){
for(int i=0 ; i<6 ; i++){
for(int j=0 ; j<6 ; j++){
if(i==0) nxt[i][j] = true;
else nxt[i][j] = false;
vis[i][j] = false;
}
}
nxt[1][2] = nxt[1][3] = nxt[1][5] = true;
nxt[2][1] = nxt[2][3] = nxt[2][5] = true;
nxt[3][1] = nxt[3][2] = nxt[3][4] = nxt[3][5] = true;
nxt[4][3] = nxt[4][5] = true;
nxt[5][1] = nxt[5][2] = nxt[5][3] = nxt[5][4] = true;
res[0]=1;
DFS(1, 1);
return 0;
}
|
時間複雜度分析
DFS 每層最多 $4$ 種選擇，總共有 $8$ 層，時間複雜度為 $O(4^8)$