大概刷了 50 題左右 GPE Helper 上面比較常出現的題目，根據題目類型分類做一些筆記，方便之後複習。

DFS&BFS
Problem UVA
11006 Rank the Languages 10336
22171 Dungeon Master 532
Tree&Graph
Problem UVA
2009-17 Binary tree traversals
10038 Disk Tree 1556
10602 Longest Paths 10000
24731 Roads in the North 10308

DFS & BFS

Rank the Languages

UVA 10336

題目大意

給定一張地圖，上面標有小寫英文字母，字母 k 的區域代表裡面所有的字母皆為字母 k，要求計算每個字母所有的區域數量，並且將他們排序。

解題方法

每次使用 DFS 尋找相鄰的相同字母，並將其標示為其他字元 (題目中不會使用到的) 代表已經處理過，使用 vector 來儲存每個字母的區域數量，最後用自訂的 cmp 函數來排序。

注意事項
  • 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
#include <bits/stdc++.h>

using namespace std;

int n, h, w, dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool cmp(pair<char, int> p1, pair<char, int> p2){
    if(p1.second != p2.second) return p1.second > p2.second;
    return p1.first < p2.first;
}

void dfs(vector<vector<char>> &world, int x, int y, char cur){
    world[x][y] = 'A'; //改為用不到的字母
    for(int i = 0; i < 4; i++){
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if(nx >= 0 && nx < h && ny >= 0 && ny < w && world[nx][ny] != 'A' && cur == world[nx][ny]){
            dfs(world, nx, ny, cur);
        }
    }
    return;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h >> w;
        vector<pair<char, int>> v;
        vector<vector<char>> world(h, vector<char>(w));
        for(int p = 0; p < h; p++){
            for(int q = 0; q < w; q++){
                cin >> world[p][q];
            }
        }
        for(int p = 0; p < h; p++){
            for(int q = 0; q < w; q++){
                if(world[p][q] != 'A'){ //當前位置還沒處理過
                    int b = 0;
                    for(int k = 0; k < v.size(); k++){
                        if(v[k].first == world[p][q]){
                            (v[k].second)++;
                            b = 1;
                            break;
                        }
                    }
                    if(b == 0) v.push_back({world[p][q], 1});
                    dfs(world, p, q, world[p][q]);
                }
            }
        }
        sort(v.begin(), v.end(), cmp); //照區域數量排序
        cout << "World #" << i << endl;
        for(int k = 0; k < v.size(); k++){
            cout << v[k].first << ": " << v[k].second << endl;
        }
    }
    return 0;
}

Dungeon Master

UVA 532

題目大意

給定一個三維的迷宮，求出是否能夠從起點到達終點，如果可以的話必須印出最短時間。

解題方法

從起點開始用 BFS 尋找路徑，如果能夠到達終點，此時的時間一定是最短的。

注意事項
  • BFS 時可以前進的方向有 6 個。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

int l, r, c, ans, dir[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};

int bfs(vector<vector<vector<char>>>& v, vector<int> s, vector<int> e) {
    queue<vector<int>> q;
    q.push({s[0], s[1], s[2], 0});
    while(!q.empty()){
        int x = (q.front())[0], y = (q.front())[1], z = (q.front())[2], step = (q.front())[3];
        q.pop();
        if(x == e[0] && y == e[1] && z == e[2]) return step;
        for(int d = 0; d < 6; d++){
            int nx = x + dir[d][0], ny = y + dir[d][1], nz = z + dir[d][2];
            if(nx >= 0 && nx < l && ny >= 0 && ny < r && nz >= 0 && nz < c && v[nx][ny][nz] != '#'){
                v[nx][ny][nz] = '#';
                q.push({nx, ny, nz, step + 1});
            }
        }
    }
    return -1;
}

int main(){
    while(cin >> l >> r >> c && l != 0 && r != 0 && c != 0){
        ans = 30000;
        vector<vector<vector<char>>> v(l, vector<vector<char>>(r, vector<char>(c)));
        vector<int> s(3), e(3);
        for(int i = 0; i < l; i++){
            for(int j = 0; j < r; j++){
                for(int k = 0; k < c; k++){
                    cin >> v[i][j][k];
                    if(v[i][j][k] == 'S') s = {i, j, k};
                    if(v[i][j][k] == 'E') e = {i, j, k};
                }
            }
        }
        int ans = bfs(v, s, e);
        if(ans == -1) cout << "Trapped!" << endl;
        else cout << "Escaped in " << ans << " minute(s)." << endl;
    }
    return 0;
}

Tree & Graph

Binary tree traversals

題目大意

已知一個二元樹的前序和中序遍歷，求出其後序遍歷。

解題方法

利用遞迴重構出二元樹，之後求後續遍歷並輸出。

注意事項
  • 重構樹的過程要注意左右子樹的元素數量。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

int n, m;

struct node{
    char c;
    node* left;
    node* right;
    node(char k){
        c = k;
    }
};

node* buildTree(vector<char> pre, vector<char> in, int pre_l, int pre_r, int in_l, int in_r){
    if(pre_l > pre_r || in_l > in_r) return NULL;
    int len;
    for(int i = in_l; i <= in_r; i++){ //求左子樹的元素數量
        if(pre[pre_l] == in[i]){
            len = i - in_l;
            break;
        }
    }
    node* root = new node(pre[pre_l]);
    root -> left = buildTree(pre, in, pre_l + 1, pre_l + len, in_l, in_l + len - 1); //重構左子樹
    root -> right = buildTree(pre, in, pre_l + len + 1, pre_r, in_l + len + 1, in_r); //重構右子樹
    return root;
}

void postorder(node* root){ //後序遍歷
    if(root == NULL) return;
    postorder(root -> left);
    postorder(root -> right);
    cout << root -> c << " ";
}

int main(){
    cin >> m;
    while(m--){
        cin >> n;
        vector<char> pre(n), in(n);
        for(int i = 0; i < n; i++){
            cin >> pre[i];
        }
        for(int i = 0; i < n; i++){
            cin >> in[i];
        }
        node* root = buildTree(pre, in, 0, n - 1, 0, n - 1);
        postorder(root);
        cout << endl;
    }
    return 0;
}

Disk Tree

UVA 1556

題目大意

給定許多行的資料夾路徑，輸出所有資料夾的結構，同一層內資料夾依照字典序排列，並且根據層級補上對應的空格。

解題方法

輸入時把 \ 替換為空格，並且利用 stringstream 分割每個資料夾，使用 字典樹 儲存資料夾，最後 DFS 遍歷每個節點中的 Map 以達到照字典序排列的要求。

補充資料： 演算法筆記-字典樹

注意事項
  • 字典樹的結構比較複雜，需要多留意。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

struct node{
    string name;
    map<string, int> nextNode;

    node(){
        nextNode.clear();
    }
    node(string s){
        name = s;
        nextNode.clear();
    }
};

vector<node> dict;

void insertNode(vector<string> v){
    int cur = 0;
    for(int i = 0; i < v.size(); i++){
        if((dict[cur].nextNode).count(v[i]) == 0){ //沒有此資料夾
            dict.push_back(node(v[i]));
            dict[cur].nextNode[v[i]] = dict.size() - 1;
        }
        cur = dict[cur].nextNode[v[i]];
    }
}

void dfs(int cur, int d){
    if(cur){
        for(int i = 1; i < d; i++){
            cout << " ";
        }
        cout << dict[cur].name << endl;
    }
    if(!(dict[cur].nextNode).empty()){
        for(auto k = dict[cur].nextNode.begin(); k != dict[cur].nextNode.end(); k++){ //照字典序遍歷
            dfs(k -> second, d + 1);
        }
    }
}

int n;
string str, s;

int main(){
    while(cin >> n){
        dict.clear();
        dict.push_back(node(""));
        while(n--){
            cin >> str;
            for(int i = 0; i < str.size(); i++){
                if(str[i] == '\\') str[i] = ' '; //替換為空格
            }
            stringstream ss(str);
            vector<string> tmp;
            while(ss >> s){
                tmp.push_back(s);
            }
            insertNode(tmp);
        }
        dfs(0, 0);
        cout << endl;
    }
    return 0;
}

Longest Paths

UVA 10000

題目大意

給定一張有向的無環圖以及起點，保證從起點可以到任何一個點，求出離起點最遠的點以及距離。

解題方法

將邊權設為 -1，因為是無環圖所以不用擔心負環，使用 Bellman-Ford Algorithm 求出最短的距離，之後再將距離轉為正數就是題目要求的最遠距離。

注意事項
  • 邊權為負時不能用 Dijkstra 演算法。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

void solve(vector<pair<int, int>> v, int n, int s, int c){
    vector<int> dis(n, INT_MAX);
    dis[s - 1] = 0;

    for(int k = 1; k < n; k++){
        for(int i = 0; i < v.size(); i++){
            if(dis[v[i].first] - 1 < dis[v[i].second]){
                dis[v[i].second] = dis[v[i].first] - 1;
            }
        }
    }
    int m = INT_MAX, ans;
    for(int i = 0; i < dis.size(); i++){ //找最小值
        if(dis[i] < m){
            ans = i;
            m = dis[i];
        }
    }
    cout << "Case " << c << ": The longest path from " << s << " has length " << -m << ", finishing at " << ans + 1 << "." << endl << endl;
    return;
}

int n, s, a, b, c = 0;

int main(){
    while(cin >> n && n != 0){
        cin >> s;
        c++;
        vector<pair<int, int>> v;
        while(cin >> a >> b && a != 0 && b != 0){
            v.push_back({a - 1, b - 1});
        }
        solve(v, n, s, c);
    }
    return 0;
}

Roads in the North

UVA 10308

題目大意

給定一棵樹，求出樹中最長的兩點距離。

解題方法

題意同求樹的直徑 (最長兩點距離)，隨便選一個點作為根開始，利用 DFS 遍歷每個點，將遍歷到的點作為中繼點，求其離葉節點的最長與次長距離，相加並與當前最大值比較。

注意事項
  • 注意輸入的格式，不同的 case 間以空行區隔。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

void addRoad(string str, vector<pair<int, int>> adj[]){
    stringstream ss(str);
    int a, b, c;
    ss >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
    return;
}

int dfs(vector<pair<int, int>> adj[], int x, int px, int &d){
    int h1 = 0, h2 = 0;
    for(int i = 0; i < adj[x].size(); i++){
        if(adj[x][i].first != px){
            int h = dfs(adj, adj[x][i].first, x, d) + adj[x][i].second;
            if(h > h1){ //檢查是否為最長、次長邊
                h2 = h1;
                h1 = h;
            }
			else if(h > h2) h2 = h;
        }
    }
    d = max(d, h1 + h2); //檢查是否是最長距離
    return h1;
}

string str;

int main(){
    while(getline(cin, str)){
        int d = 0;
        vector<pair<int, int>> adj[10001];
        addRoad(str, adj);
        while(getline(cin, str) && str != "\0"){
            addRoad(str, adj);
        }
        dfs(adj, 1, 1, d);
        cout << d << endl;
    }
    return 0;
}