C - 流れ Editorial

Time Limit: 2 sec / Memory Limit: 64 MB

Description

whw*hのグリッドがある.

グリッド上のおのおののマスには,高さが設定されている.

今,いくつかのマスの上から液体を注ぐ.

あるマスの上に液体が存在し,そのマスの高さよりもそこから隣接するマスの高さの方が低いとき,液体は隣接するマスへ広がっていく.ただし,グリッド上の2つのマスは辺を共有するときに隣接していると見なす.

液体が広がるマスの個数を求めよ.

Input

入力は複数のテストケースからなる. 入力の終わりは,3つの0のみを含んだ行で示される. 各テストケースは,以下の形式で与えられる.

ww hh pp
z00z_{00} z01z_{01}z0(w1)z_{0(w-1)}
z10z_{10} z11z_{11}z1(w1)z_{1(w-1)}z(h1)0z_{(h-1)0} z(h1)1z_{(h-1)1}z(h1)(w1)z_{(h-1)(w-1)}
x1x_1 y1y_1xpx_p ypy_p
  • 1wh201 ≦ w,h ≦ 20
  • 0pwh0 ≦ p ≦ wh
  • 0zij1000 ≦ z_{ij} ≦ 100
  • 0xi<w0 ≦ x_i < w
  • 0yi<h0 ≦ y_i < h

テストケースの1行目には,3つの整数whpw,h,pが書かれている. whw,hはそれぞれグリッドの横幅と縦幅を表し,ppは液体を注ぐ回数を表す.

続くhh行には,それぞれw個の整数zijz_{ij}が書かれている. zijz_{ij}は(jjii)のマスの高さを表す.

続くpp行にはそれぞれ2個の整数xix_iyiy_iが書かれている. xix_iyiy_iは(xix_iyiy_i)のマスに液体を注ぐことを示す.

ただしすでに液体を注いだマスにもう一度液体を注ぐこともある.

テストケースの数は1つのファイルにつき20個以下であることが保証されている.

Output

各テストケースに対して,液体が広がるマスの個数を1行に出力せよ.

Sample InputCopy

Copy
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 OutputCopy

Copy
1
3
0
5

Source Name

ふか杯 5th Contest


2025-04-05 (Sat)
03:17:42 +00:00