1178 File Path – PAT甲级真题

The figure shows the tree view of directories in Windows File Explorer. When a file is selected, there is a file path shown in the above navigation bar. Now given a tree view of directories, your job is to print the file path for any selected file.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10^3), which is the total number of directories and files. Then N lines follow, each gives the unique 4-digit ID of a file or a directory, starting from the unique root ID 0000. The format is that the files of depth d will have their IDs indented by d spaces. It is guaranteed that there is no conflict in this tree structure.

Then a positive integer K (≤100) is given, followed by K queries of IDs.

Output Specification:

For each queried ID, print in a line the corresponding path from the root to the file in the format: 0000->ID1->ID2->...->ID. If the ID is not in the tree, print Error: ID is not found. instead.

Sample Input:

14
0000
1234
2234
3234
4234
4235
2333
5234
6234
7234
9999
0001
8234
0002
4 9999 8234 0002 6666

Sample Output:

0000->1234->2234->6234->7234->9999
0000->1234->0001->8234
0000->0002
Error: 6666 is not found.

题目大意：该图显示了Windows文件资源管理器中目录的树状视图。当选择文件时，上方导航栏会显示文件路径。现在给定一个目录的树状视图，任务是打印任何选定文件的文件路径。第一行给出一个正整数N，表示目录和文件的总数。然后是N行，每行给出一个文件或目录的唯一的4位数ID，从唯一的根ID 0000 开始。格式是深度为d的文件将其ID缩进d个空格。然后给出一个正整数K，随后是K个查询的ID。对于每个查询的ID，在一行中按格式打印从根到文件的相应路径：0000->ID1->ID2->…->ID。如果ID不在树中，则打印错误：ID is not found.

分析：superior记录每一个编号的上级编号，last记录每层文件的上级文件夹，root记录根文件夹，ans中存储最后输出的文件访问路径。用map记录信息，注意带空格的整行字符串的输入需要用到getline，并且在普通cin输入和整行getline输入的时候会需要一个getchar帮忙一下。
每次输入一个文件目录，先找到它有几个(I个)空格，然后记录一下它的上级信息，并且把它作为最新的下一层的文件夹的上级目录。最后输入查找的目标，不在map里就表示没有，有的话就整理成题目所需输出的顺序输出即可～

#include <iostream>
#include <string>
#include <map>
using namespace std;
int N, K;
string s, root, ans;
map<string, string> superior;
map<int, string> last;
int main() {
    cin >> N >> root;
    last[1] = root;
    superior[root] = root;
    getchar();
    for (int i = 1, I; i < N; i++) {
        getline(cin, s);
        I = 0;
        while (s[I] == ' ') ++I;
        superior[s.substr(I)] = last[I];
        last[I + 1] = s.substr(I);
    }
    cin >> K;
    while (K--) {
        cin >> s;
        if (!superior.count(s)) cout << "Error: " << s << " is not found.\n";
        else {
            ans = "\n";
            while (s != root) {
                ans = "->" + s + ans;
                s = superior[s];
            }
            cout << root << ans;
        }
    }
    return 0;
}

#include <iostream>

#include <string>

#include <map>

using namespace std;

int N, K;

string s, root, ans;

map<string, string> superior;

map<int, string> last;

int main() {

cin >> N >> root;

last[1] = root;

superior[root] = root;

getchar();

for (int i = 1, I; i < N; i++) {

getline(cin, s);

I = 0;

while (s[I] == ' ') ++I;

superior[s.substr(I)] = last[I];

last[I + 1] = s.substr(I);

}

cin >> K;

while (K--) {

cin >> s;

if (!superior.count(s)) cout << "Error: " << s << " is not found.\n";

else {

ans = "\n";

while (s != root) {

ans = "->" + s + ans;

s = superior[s];

}

cout << root << ans;

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版