题解 | #路径打印#
路径打印
http://www.nowcoder.com/practice/64b472c9bed247b586859978d13145ad
递归进行路径打印
代码如下:
#include <bits/stdc++.h>
using namespace std;
void print_space(int d) {
for (int i = 0; i < d; ++i) cout << " ";
}
void dfs(int l, int r, int d, const vector<vector<string>>& tokens) {
// 参数意义 [l, r)表示打印下标为[L, r)的区域,d表示打印深度
if (l + 1 == r && d >= tokens[l].size()) return ;
int cur = l;
for (int i = l; i < r; ++i, ++cur) {
while (cur + 1 < r && d < tokens[cur].size() && d < tokens[cur + 1].size() && tokens[cur][d] == tokens[cur + 1][d]) ++cur;
print_space(d);
cout << tokens[cur][d] << endl;
dfs(i, cur + 1, d + 1, tokens);
i = cur;
}
}
void solve(int n) {
vector<string> ss(n);
for (int i = 0; i < n; ++i) {
cin >> ss[i];
if (ss[i].back() != '\\') {
ss[i] += '\\';
}
}
vector<vector<string>> tokens(n); // 把所有的路径存到一个二维数组
for (int i = 0; i < n; ++i) {
auto& s = ss[i];
int m = s.size(), idx = 0;
for (int j = 0; j < m; ++j, ++idx) {
while (idx < m && s[idx] != '\\') ++idx; // 这一步主要是为了方便统一处理,看了样例有的最后一个并不是\结尾,所以统一加了\ 方便处理
tokens[i].push_back(s.substr(j, idx - j));
j = idx;
}
}
sort(tokens.begin(), tokens.end());
dfs(0, n, 0, tokens); // 递归进行打印
}
int main() {
int n;
while (cin >> n, n) {
solve(n);
cout << endl; // 我真的是醉了,没看到每个测试样例后跟一个空行,找了半天bug
}
return 0;
}