e676: 00469 - Wetlands of Florida
Tags : DFS、BFS
Accepted rate : 41人/46人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-11-12 17:51

Content

一家建築公司在佛羅里達州擁有一大片房地產。最近,該公司決定開發此物業。然而,在對該財產進行檢查時,發現該土地在各個地點都有沼澤池塘等。
這讓公司的所有者感到震驚,因為他們來自別的州,並不熟悉佛羅里達的濕地。
情況非常嚴峻,業主不知道這樣的水域該如何轉化成美麗的湖泊,從而增加周圍土地的價值,於是他們有點想放棄此建設項目。
幸運的是,這個問題引起了一位聰明的FIU畢業生的注意,他提出了解決方案,所以此建築項目又重啟了。
工程師通過網格將建築工地分成均勻的方形單元,以使每個方形單元完全包含土地或水域。
現在,工程師要回答的問題如下:"給出一個裝有水的網格單元的行數和列數,該單元的水域面積是多少。"
(面積是根據相鄰同樣網格的數量來計算。上、下、左、右、對角線都屬於相鄰的單元。)

Input

輸入第一行為一個正整數T,代表有幾組測資。
每組測資第一行為一空白行。
接下來n (0 < n ≤ 99)行,每行包含m (0 < m ≤ 99)個字元,代表土地狀況。
字元只會有'L'(土地)和'W'(水域)。
接下來k (k > 0)行,每行包含一對整數i和j,代表要詢問的單元座標。

Output

對於每組測資,輸出詢問單元格的水域面積為多少。
每組測資間需用空白行分隔。

Sample Input #1
1

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLWLWLLLL
LLLLLLLLL
3 2
7 5
Sample Output #1
12
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
DFS、BFS
出處:
UVA [管理者:
ig99lp33lp33 (위즈원)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」