切換
舊版
前往
大廳
主題

ZeroJudge - f170: m5a1-尋找小狗(Dog) 解題心得

Not In My Back Yard | 2020-08-13 14:41:20 | 巴幣 0 | 人氣 349

題目連結:


題目大意:
第一列給定一正整數 N (2 ≦ N ≦ 10 ^ 3),代表一個有 N × N 的網格地圖。接著的一列給定兩非負整數,代表出發座標(先 H 座標再 L 座標,其中 H 座標代表所在列數減一之值、 L 座標代表所在行數減一之值。)。最後有 N 列輸入,每列給定 N 個整數,代表這 N × N 的每格網格之「高度」。

對於每個網格,該格可以往上下左右的格子走去,但是要滿足:不得超出地圖外、原先網格與目標網格之高度差不得超過 2 。

試問從給定的 H 、 L 座標出發,最多可以走到多少個相異格子?



範例輸入:
範例輸入 1:
5
2 2
2 3 4 7 8
1 5 2 3 7
6 5 3 4 8
2 4 6 7 1
1 6 3 4 3

範例輸入 2:
4
2 1
6 4 8 3
8 8 8 3
8 5 4 4
1 3 3 9

範例輸入 3:
3
1 1
4 9 4
4 5 9
4 3 3


範例輸出:
範例輸出 1:
17

範例輸出 2:
8

範例輸出 3:
6


解題思維:
典型的廣度優先搜尋(Breadth First Search,BFS)之題型,如此題。但是擴散的條件從只能往相同字元走,變為此題的高度差不得超過 2 。




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

創作回應

更多創作