這一題的大意是給出了一個windows的文件夾目錄，讓我們按照所屬的目錄關系，來找相應的目錄是否存在，如果存在，就輸出找到該文件的路徑，如果不存在輸出error
我的思路是用合適的樹形結構保存下來目錄的所屬關系，然后用dfs遍歷樹的方式，遞歸查找要求的目錄，在遞歸的過程中用數組保存路徑，最后跑完dfs，判斷這個數組是不是為空，不為空輸出數組即可。
可以畫出樹形結構圖，來根據圖示寫樹形結構
我的思路是:
struct node
{vector<int> data;//當前深度有哪些節點 vector<vector<int>> child;//它們的孩子有哪些//其中要標記誰是誰的孩子。
}tree[1005];
我看網上有題解用哈希表存儲的，但我看到題的第一眼就想出這樣的存圖方式。。。
事實證明這樣寫也是可以的，存儲輸入的方式如下：
cin>>N;getchar();for(int i=0;i<N;i++){tree[i].child.resize(105);} for(int i=0;i<N;i++){string s;getline(cin,s);int level=s.size()-4;//表示處于哪一層 string temp=s.substr(level,4);int x=stoi(temp);//最多有maxx層 if(maxx<level){maxx=level;}//表示第level層的數據 tree[level].data.push_back(x);if(level!=0){//如果不是根節點，那么需要把該節點它的父親找到 //因為輸入的原因，一個節點的父親一定是它上一層節點的最后一個 int nowlast=tree[level-1].data.size()-1;//這就是最后一個 //所以上一個節點的孩子節點有著落了 tree[level-1].child[nowlast].push_back(x);}}/*for(int i=0;i<N;i++){for(int j=0;j<tree[i].data.size();j++){cout<<tree[i].data[j]<<" ";cout<<endl;for(int k=0;k<tree[i].child[j].size();k++){cout<<tree[i].child[j][k]<<" ";}cout<<endl;}cout<<endl;}*/int K;cin>>K;//輸入K次詢問 for(int i=0;i<K;i++){int q;cin>>q;flag=0;//對于每一次詢問，我們去找是否在樹中有這個點。 //從根節點開始找 dfs(0,0,q);if(ans.size()!=0){for(int j=0;j<ans.size();j++){if(j!=0)cout<<"->";printf("%04d",ans[j]);}cout<<endl;ans.clear();}else{cout<<"Error: "<<q<<" is not found.";cout<<endl;} }
我們用結構體來構造一個樹的某一層的節點情況，tree[i]表示第i層的情況，這一層有多少個節點，每一個節點有哪些孩子(用二維數組來存儲），在dfs的時候，我們只需要判斷這一層的節點是不是上一層節點的孩子，如果是，就可以繼續從這個節點往下走，如果不是則去找這一層的其他節點，同樣的判斷是不是上一層節點的孩子，如果是，可以繼續dfs下一層。
如果某一層的某一個節點等于要找的節點直接標記后，不停return即可。
如果dfs的深度比給出的最大層數要大，則return（遞歸邊界）
完整代碼如下：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
int N;
struct node
{vector<int> data;//當前深度有哪些節點 vector<vector<int>> child;//它們的孩子有哪些//其中要標記誰是誰的孩子。
}tree[105];
int maxx;
bool flag=0;
vector<int> ans;
void dfs(int level,int now,int q)
{//如果當前層比最高層還要大，說明要返回了，遞歸邊界 if(level>maxx){return;}else{//假設現在是第0層//那么我們需要看一下第0層有沒有符合條件的//第0層不用管是不是上一個的孩子//但以后需要管 for(int i=0;i<tree[level].data.size();i++){if(level!=0){//必須保證是符合題目要求的 //才可以選擇繼續 //我們只需判斷這里的節點是不是上一層它的父親的孩子 bool f=0; //從上一次父親的孩子中以一比對 for(int j=0;j<tree[level-1].child[now].size();j++){if(tree[level-1].child[now][j]==tree[level].data[i]){//說明是，可以往后面進行 ans.push_back(tree[level].data[i]); //cout<<ans.back()<<" "; f=1;break;}}if(f==0){continue;}}else{ans.push_back(tree[level].data[i]);//cout<<ans.back()<<" "; }if(tree[level].data[i]==q){//說明符合條件flag=1;return;//反之不符合 } //在這個層沒有找到q，往下一層找，找的時候注意保證，下一層的節點是上一層i的孩子 dfs(level+1,i,q);if(flag==1){return ;}ans.pop_back();} }
}
int main()
{//ios::sync_with_stdio(0),cin.tie(0),cout.tie(cin>>N;getchar();for(int i=0;i<N;i++){tree[i].child.resize(105);} for(int i=0;i<N;i++){string s;getline(cin,s);int level=s.size()-4;//表示處于哪一層 string temp=s.substr(level,4);int x=stoi(temp);//最多有maxx層 if(maxx<level){maxx=level;}//表示第level層的數據 tree[level].data.push_back(x);if(level!=0){//如果不是根節點，那么需要把該節點它的父親找到 //因為輸入的原因，一個節點的父親一定是它上一層節點的最后一個 int nowlast=tree[level-1].data.size()-1;//這就是最后一個 //所以上一個節點的孩子節點有著落了 tree[level-1].child[nowlast].push_back(x);}}/*for(int i=0;i<N;i++){for(int j=0;j<tree[i].data.size();j++){cout<<tree[i].data[j]<<" ";cout<<endl;for(int k=0;k<tree[i].child[j].size();k++){cout<<tree[i].child[j][k]<<" ";}cout<<endl;}cout<<endl;}*/int K;cin>>K;//輸入K次詢問 for(int i=0;i<K;i++){int q;cin>>q;flag=0;//對于每一次詢問，我們去找是否在樹中有這個點。 //從根節點開始找 dfs(0,0,q);if(ans.size()!=0){for(int j=0;j<ans.size();j++){if(j!=0)cout<<"->";printf("%04d",ans[j]);}cout<<endl;ans.clear();}else{cout<<"Error: "<<q<<" is not found.";cout<<endl;} }return 0;}
在寫的時候我一開始有一個bug一直修正不了：
該continue的地方寫成了break，導致少比較一些節點。
最后借助ai才搞定，中間不停的懷疑自己的思路究竟對不對，
自己的debug能力仍需要提升。
)
