UVA 看圖寫樹：多叉樹括號表示法的 DFS 構建

UVA「看圖寫樹」：給定字符矩陣表示的多叉樹（節點為非空格字符，子節點通過 '|' 和 '-' 連接），輸出括號表示法。本文解析 DFS 遞歸解析邏輯：從根節點開始，檢查下方 '|' 和 '-' 尋找子節點。

輸入格式分析

• 矩陣行數不固定，以 '#' 行結束。
• 節點：除 '-', '|', ' ' 外的可見字符。
• 連接規則：
• 節點正下方一格為 '|' 表示有子節點。
• '|' 下方一行為連續 '-'，覆蓋所有子節點頂部。
• '-' 下方一行為子節點字符。

遞歸解析算法

1. 讀入所有行到 buf[row][col]。
2. 從第 0 行掃描第一個非空格字符作為根。
3. 遞歸函數 dfs(r, c) 處理位置 (r,c) 的節點：
4. 輸出 buf[r][c] + "("。
5. 若 buf[r+1][c] == '|' 且 r+1 < 行數：
6. 沿 buf[r+2] 向左找到最左邊的 '-'，記為 start_col。
7. 從 start_col 向右掃描 '-'，對每個位置 col，若 buf[r+3][col] != ' '，遞歸 dfs(r+3, col)。
8. 輸出 ")"。

完整代碼（C++）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100;
char buf[MAXN][MAXN];
int rows;

void dfs(int r, int c) {
    if (r+1 < rows && buf[r+1][c] == '|') {
        // 找最左邊的 '-'
        int col = c;
        while (col-1 >= 0 && buf[r+2][col-1] == '-') col--;
        // 掃描所有 '-' 覆蓋的子節點
        for (int i = col; i < MAXN && buf[r+2][i] == '-'; ++i) {
            if (r+3 < rows && buf[r+3][i] != ' ') {
                cout << buf[r+3][i] << "(";
                dfs(r+3, i);
            }
        }
    }
    cout << ")";
}

int main() {
    int T; cin >> T; getchar();
    while (T--) {
        rows = 0;
        memset(buf, 0, sizeof(buf));
        while (fgets(buf[rows], MAXN, stdin)) {
            buf[rows][strcspn(buf[rows], "\n")] = 0; // 去換行
            if (strcmp(buf[rows], "#") == 0) break;
            rows++;
        }
        cout << "(";
        if (rows > 0) {
            for (int i = 0; i < strlen(buf[0]); ++i) {
                if (buf[0][i] != ' ') {
                    cout << buf[0][i] << "(";
                    dfs(0, i);
                    break;
                }
            }
        }
        cout << ")" << endl;
    }
    return 0;
}

關鍵細節

1. 輸入讀取：fgets 讀整行，去除換行符，遇到 "#" 停止。
2. 邊界檢查：每次訪問 buf[r][c] 前確保 r < rows。
3. 最左 '-' 定位：從父節點列向左掃描，因 '-' 連續覆蓋所有子節點。
4. 子節點行：在 '-' 下方一行 (r+3)。
5. 輸出格式：每個節點輸出 字符(，遞歸處理子女，最後輸出 )。整棵樹外層包一對 ()。

樣例驗證

輸入：
2
A
|
-------------
B C D
| | -----
E F G
#
e
| -----
f g
#

輸出：
(A(B()C(E()F())D(G())))
(e(f()g()))

總結

本題是「字符矩陣解析樹結構」的經典問題。關鍵在於理解『| - 子節點』的幾何佈局規則，並用遞歸 DFS 自然映射樹的層次結構。代碼簡潔，核心邏輯集中在 dfs 中的「向左找最左 '-', 向右掃描子節點」兩步。注意邊界條件與輸入讀取細節即可 AC。