NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2019高中組初賽
 F.地底探險

作者 主題: F.地底探險  (閱讀 143 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 243
    • 檢視個人資料
F.地底探險
« 於: 十一月 12, 2020, 03:12:37 pm »

就是要你實作出一顆樹,因為有 go back 的操作,所以你的指標要是雙向的,
比較容易超時的操作是在用一個節點下新增非常多的子節點,
然後請你輸出該點的所有子節點(註:題目要求只要輸出前100個),
因此子節點的記錄,我是使用 map 來完成這個操作,
整個程式主要用到的陣列如下:
代碼: [選擇]
int parent[50001];
string name[50001], path[101];
map<string,int> child[50001];
parent[ i ]記錄第 i 號節點的上層編號,
name[ i ] 記錄第 i 號節點的名字,
child[ i ]則是記錄第 i 號節點的子節點有哪些,
path是 where am I 或 where can I go 時用來輸出用的。

而主程式的操作如下:
代碼: [選擇]
int n, cur, node, pn, i;
string s, op, obj, t;
stringstream sin;
map<string,int>::iterator it;
name[0]="ground";
parent[0]=-1;
child[0].clear();
node=1;
cur=0;
cin >> n;
getline(cin, s);
while (n--)
{
getline(cin, s);
sin.clear();
sin.str(s);
sin >> op >> obj;
if (op=="dig")
{
it=child[cur].find(obj);
if (it==child[cur].end()) // Not found
{
name[node]=obj;
parent[node]=cur;
child[node].clear();
child[cur].insert(pair<string,int>(obj, node));
//child[cur][obj]=node;
node++;
}
else
{
t="'"+obj+"' exist!";
AddAnswer(t);
}
}
else if (op=="collapse")
{
it=child[cur].find(obj);
if (it==child[cur].end()) // Not found
{
t="'"+obj+"' not exist!";
AddAnswer(t);
}
else
{
child[cur].erase(it);
}
}
else if (op=="go")
{
if (obj=="to")
{
sin >> obj;
it=child[cur].find(obj);
if (it==child[cur].end()) // Not found
{
t="'"+obj+"' not exist!";
AddAnswer(t);
}
else
{
cur=child[cur][obj];
}
}
else // back
{
if (cur==0) // ground
{
t="You are on the ground!";
AddAnswer(t);
}
else cur=parent[cur];
}
}
else // where
{
if (obj=="am")
{
int ccur=cur;
for (pn=0; pn<=100; )
{
path[pn++]=name[ccur];
if (ccur==0) break;
ccur=parent[ccur];
}
if (pn<=100)
{
t=path[pn-1];
for (i=pn-2; i>=0; i--)
{
t+=(" -> "+path[i]);
}
}
else
{
t="-> "+path[99];
for (i=98; i>=0; i--)
{
t+=(" -> "+path[i]);
}
}
AddAnswer(t);
}
else // can
{
for (it=child[cur].begin(), pn=0; it!=child[cur].end(); ++it)
{
path[pn++]=it->first;
if (pn==101)
{
path[100]="...";
break;
}
}
if (pn>0) t=path[0];
else t="";
for (i=1; i<pn; i++)
{
t+=(" "+path[i]);
}
AddAnswer(t);
}
}
}
PrintAnswer();
原始的 AddAnswer 函數使用的是 char 陣列,而我將它改成使用 string。(注意要加一個換行字元)
« 上次編輯: 十一月 12, 2020, 03:14:46 pm 由 sagit »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2019高中組初賽
 F.地底探險