解題區/解題區 - UVa

UVa 12841 - In Puzzleland (III)

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定一個無向圖，每一個頂點由大寫字母表示，找到從起點到終點，並且經過所有點 (每一個點最多經過一次) 的路徑，輸出最小字典順序的路徑。

Sample Input

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
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
4 5
L N I K
L N
I L
I N
K N
K I

Sample Output

1
2
3
Case 1: AVCDYFUBWXEZ
Case 2: impossible
Case 3: LINK

Solution

一開始想說點數最多才 15，根據 D&C 的作法，拆分成兩塊 (分別有 N/2 個點)，其中一塊從起點開始、另一塊以終點結束的路徑。隨後再把兩塊組合在一起，找字典順序最小即可，看來是測資太多，很容易就 TLE，不過這方法是最穩定的，建表最慘需要 O(2^15 * 7!)。

由於可行狀態太多，也就是好死不死給一張接近完全圖，那上述的算法會超慢，如果要計算方法總數可能才會用到上述解法。而這一題直接 dfs 搜索，並且確保每一步走下去時，剩下的節點會在同一個連通元件上，不會拆分成兩塊。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector> 
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[26];
char path[32];
int n, m, st, ed, used[26];
int bused[26] = {}, tused = 0;
int bfs(int u, int comp) {
    tused++;
    int cnt = 0, v;
    queue<int> Q;
    Q.push(u), bused[u] = tused;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        cnt++;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (bused[v] != tused && used[v] == 0) {
                bused[v] = tused;
                Q.push(v);
            }
        }
    }
    return cnt == comp;
}
int dfs(int idx, int u) {
    path[idx] = u + 'A';
    if (idx < n - 1 && used[ed])	return 0;
    if (idx == n-1) {
        path[n] = '\0';
        puts(path);
        return 1;
    }
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (used[v] || !bfs(v, n - idx - 1))	
            continue;
        used[v] = 1;
        if(dfs(idx+1, v))	return 1;
        used[v] = 0;
    }
    return 0;
}
int main() {
    int testcase, cases = 0;
    int x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        char name[26][4], s1[4], s2[4], buf[26];
        int mg[26][26] = {};
        for (int i = 0; i < 26; i++)
            g[i].clear();
        for (int i = 0; i < n; i++)
            scanf("%s", name[i]);
        for (int i = 0; i < m; i++) {
            scanf("%s %s", s1, s2);
            x = s1[0] - 'A', y = s2[0] - 'A';
            mg[x][y] = mg[y][x] = 1;
        }
        st = name[0][0] - 'A', ed = name[n-1][0] - 'A';
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                if (mg[i][j])
                    g[i].push_back(j);
            }
        }
        printf("Case %d: ", ++cases);
        memset(used, 0, sizeof(used));
        used[st] = 1;
        int f = dfs(0, st);
        if (!f)	puts("impossible");
    }
    return 0;
}
/*
3
12 14
A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
50
4 5
L N I K
L N
I L
I N
K N
K I
*/