ETH官方钱包

前往
大廳
主題

ZeroJudge - g308: pB. 跳跳布朗尼(Brownie) 解題心得

Not In My Back Yard | 2021-09-19 00:00:10 | 巴幣 2 | 人氣 305

題目連結(jié):


題目大意:
輸入第一列給定兩正整數(shù) N 、 T(1 ≦ N ≦ 1000,0 ≦ T < N),代表現(xiàn)在有 N 個格子(編號為 0 ~ N - 1)且一開始要從編號 T 的格子開始。

接著一列給定 N 個非負(fù)整數(shù),依序代表每個編號的格子附有的傳送點(diǎn),其可以傳到給定編號之格子。

最後一列給定 N 個非負(fù)整數(shù),代表每個編號的格子是否有著布朗尼(只會是 0 或是 1,前者代表著沒有布朗尼、後者則有)。

已知每個傳送點(diǎn)只能使用一次,也就是當(dāng)傳送到先前已經(jīng)到過的位置時(shí)便不能繼續(xù)傳送到下一個位置。試問從編號 T 的格子開始傳送到無法傳送為止可以吃到幾個布朗尼?



範(fàn)例輸入:
範(fàn)例輸入 #1
6 3
0 5 0 4 2 0
0 0 1 0 1 0

範(fàn)例輸入 #2
13 12
3 0 0 5 1 3 1 2 0 8 3 0 9
1 1 0 0 1 0 1 0 1 1 1 0 0


範(fàn)例輸出:
範(fàn)例輸出 #1
2

範(fàn)例輸出 #2
3


解題思維:
就是單純地從編號 T 開始傳送並統(tǒng)計(jì)中間每個有著布朗尼的格子有多少個,直到遇到重複到過的節(jié)點(diǎn)(可以用一個布林陣列來記錄每個格子有沒有到過;也可以直接使用負(fù)責(zé)記錄「傳送」的陣列,一旦傳送過就設(shè)為「-1」,一旦遇到「-1」就代表我們到了之前到過的格子)。過程中有布朗尼的格子之總數(shù)即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創(chuàng)作回應(yīng)

相關(guān)創(chuàng)作

更多創(chuàng)作