ETH官方钱包

切換
舊版
前往
大廳
主題

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

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

題目連結(jié):


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

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

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



範(fàn)例輸入:
1

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


範(fàn)例輸出:
12
4


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

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

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

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

更多創(chuàng)作