e550. 00722 - Lakes
Tags : DFS、BFS
Accepted rate : 88人/102人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-28 21:00

Content

我們將二維空間區域劃分為均勻的正方形單元,每個正方形單元代表"land"或"water"。
考慮到"water"單元在該區域中的位置,我們感興趣的是找到水平或垂直連接的"water"單元區域,並且完全被"land"單元邊界包圍的區域的面積。
我們將會提供了任意"water"單元的位置,請判斷該位置的"water"面積。
由於我們將"water"區域的面積定義為其中的單元格數量,因此最簡單的計算面積的方法是數其中的單元格數量。
請你寫一個程式來做到這一點。

此二維空間的前提如下:
1. 此二維空間為矩形,長寬不大於99x99
2. 0代表"water"
3. 1代表"land"
4. 水可能不只一個
5. 此二維空間的邊界被"land"包圍

Input

輸入第一行是一個整數T,代表有T組測資
每組測資第一行為一空白行
接下來一行有兩個整數i、j,代表要判斷的"water"位置。
i和j皆用兩位數表示,不足兩位數則補零。
接下來多行代表要判斷的二維空間。

Output

對於每組測資,輸出該位置的"water"面積。
每組測資之間請用空白行分隔。

Sample Input #1
1

02 01
1001101
0011111
0001001
1100011
1111111
1100110
1110111
Sample Output #1
12
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :

以下為範例測資的二維區域,W代表water,L代表land,粗體代表要判斷的"water"位置。

 012345678
0LLLLLLLLL
1LLWWLLWLL
2LWWLLLLLL
3LWWWLWWLL
4LLLWWWLLL
5LLLLLLLLL
6LLLWWLLWL
7LLLLWLLLL
8LLLLLLLLL
Tags:
DFS、BFS
出處:
UVA [管理者: ig99lp33lp33(위즈원) ]


ID User Problem Subject Hit Post Date
24668 yes51851823@...(wseds) e550
別被提示騙了
653 2021-03-13 18:07