C - 流れ
Editorial
/
Time Limit: 2 sec / Memory Limit: 64 MB
Description
w*hのグリッドがある.
グリッド上のおのおののマスには,高さが設定されている.
今,いくつかのマスの上から液体を注ぐ.
あるマスの上に液体が存在し,そのマスの高さよりもそこから隣接するマスの高さの方が低いとき,液体は隣接するマスへ広がっていく.ただし,グリッド上の2つのマスは辺を共有するときに隣接していると見なす.
液体が広がるマスの個数を求めよ.
Input
入力は複数のテストケースからなる. 入力の終わりは,3つの0のみを含んだ行で示される. 各テストケースは,以下の形式で与えられる.
w h p z_{00} z_{01} … z_{0(w-1)} z_{10} z_{11} … z_{1(w-1)} … z_{(h-1)0} z_{(h-1)1} … z_{(h-1)(w-1)} x_1 y_1 … x_p y_p
- 1 ≦ w,h ≦ 20
- 0 ≦ p ≦ wh
- 0 ≦ z_{ij} ≦ 100
- 0 ≦ x_i < w
- 0 ≦ y_i < h
テストケースの1行目には,3つの整数w,h,pが書かれている. w,hはそれぞれグリッドの横幅と縦幅を表し,pは液体を注ぐ回数を表す.
続くh行には,それぞれw個の整数z_{ij}が書かれている. z_{ij}は(j,i)のマスの高さを表す.
続くp行にはそれぞれ2個の整数x_i,y_iが書かれている. x_i,y_iは(x_i,y_i)のマスに液体を注ぐことを示す.
ただしすでに液体を注いだマスにもう一度液体を注ぐこともある.
テストケースの数は1つのファイルにつき20個以下であることが保証されている.
Output
各テストケースに対して,液体が広がるマスの個数を1行に出力せよ.
Sample Input
2 2 1 1 0 0 1 1 0 2 2 1 1 0 0 1 1 1 1 1 0 100 5 5 2 5 4 5 5 5 5 3 5 1 5 5 2 1 2 5 5 3 5 3 5 5 5 5 5 5 0 0 2 2 0 0 0
Sample Output
1 3 0 5