a612. C. 水庫危機 - 旦旦解題農場

內容

隨著夏天的到來，水庫的水越來越少，地面整個呈現龜裂景像，遠遠看過去，簡直就是乾旱的土地

如下圖

而隨著變乾的土地越來越多，政府想請你幫忙計算有到目前為止整張 $n \times m$ 的地圖有多少個水區

水區的定義為如果兩個水地有共邊，則他們屬於同一個水區

以下圖為例 $3 \times 3$ 的地圖為例，$W$ 為水地，$\#$ 為乾旱的土地

$W\#W$

$\#\#W$

$W\#\#$

以上有3塊水地，分別為左上、左下、及右上三塊

而隨著時間過去，乾旱的土地只會越來越多，想請你幫忙算出每多乾旱一塊土地，剩下的水區有幾個

輸入說明

單筆測資

第一行有兩個正整數 $n, m (1 \le n, m \le 2000)$，代表土地大小為 $n \times m$ 格

接下來的 $n$ 列裡，每列會有$m$個字元 $L_{i,j} $ 代表 $L_{i,j}$ 現在的狀況

接著會有一個正整數 $d (1\le d \le 10^5)$ ，代表接下來總共有 $d$ 天

最後 $d$ 行，每行有兩個正整數 $a_i, b_i$

$(1 \le a_i \le n, 1\le b_i \le m)$

代表土地 $L_{a,b}$從水地變成乾旱的土地

$* L_{i,j} \in \{ W , \#\}$

$*保證保證選的地目前必定是水地$

$*總天數不超過一開始水地的土地$

輸出說明

輸出共 $d$ 行

每行輸出第 $d_i$ 天土地 $L_{a,b}$變乾旱後，還有幾塊水區

範例輸入

3 3
W#W
##W
W##
3
1 1
1 3
2 3

範例輸出

2
2
1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (10%): 4.0s , <10M
不公開測資點#1 (10%): 4.0s , <10M
不公開測資點#2 (10%): 4.0s , <10M
不公開測資點#3 (10%): 4.0s , <10M
不公開測資點#4 (10%): 4.0s , <10M
不公開測資點#5 (10%): 4.0s , <10M
不公開測資點#6 (10%): 4.0s , <10M
不公開測資點#7 (10%): 4.0s , <10M
不公開測資點#8 (10%): 4.0s , <10M
不公開測資點#9 (10%): 4.0s , <10M

提示：

經過第 $1$ 天

##W
##W
W##

經過第 $2$ 天

###
##W
W##

經過第 $3$ 天

###
###
W##

標籤:

出處:

DDJ Regular Contest Round#3 [管理者：

fdhs105285 (jakao)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」