切換
舊版
前往
大廳
主題

ZeroJudge - e676: 00469 - Wetlands of Florida 解題心得

Not In My Back Yard | 2020-02-18 00:08:11 | 巴幣 0 | 人氣 212

題目連結:


題目大意:
給定一正整數 T ,代表有 T 筆測試資料。每筆第一列為一空白列,接著有 n 列的輸入(n 不是一定值),每列有 m 個字元(只會是「L」或是「W」,分別代表土地及水域)。代表一 n × m 的地圖。

再接著有不定量(至少非 0)列的輸入,每列給定兩正整數 i 、 j ,代表要詢問第 i 列第 j 行的水域之面積為多少?水域的面積是由該格的水域以及其上下左右(以及那些水的上下左右,以此類推)之水域集結而成。

每組測資的輸出之間須有一空白列。



範例輸入:
1

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2
7 5


範例輸出:
12
4


解題思維:
典型的廣度優先搜尋(Breadth First Search,BFS)。如之前的題目

唯一比較麻煩的是判斷輸入的形式,可以看輸入進來的東西是字元還是數字來決定該列示要詢問還是在給定地圖。

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

創作回應

更多創作