前往
大廳
主題

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

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

題目連結:


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

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

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

已知每個傳送點只能使用一次,也就是當傳送到先前已經到過的位置時便不能繼續傳送到下一個位置。試問從編號 T 的格子開始傳送到無法傳送為止可以吃到幾個布朗尼?



範例輸入:
範例輸入 #1
6 3
0 5 0 4 2 0
0 0 1 0 1 0

範例輸入 #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


範例輸出:
範例輸出 #1
2

範例輸出 #2
3


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




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

創作回應

相關創作

更多創作