ページ

2012/06/10

[競技プログラミング][C言語][AtCoder][ふか杯]流れ

C - 流れ

時間制限 : 2sec / スタック制限 : 8MB / メモリ制限 : 64MB

Description

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

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

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

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

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

Input

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

w h p
z00 z01 … z0(w−1)
z10 z11 … z1(w−1)

z(h−1)0 z(h−1)1 … z(h−1)(w−1)
x1 y1

xp yp
1≦w,h≦20
0≦p≦wh
0≦zij≦100
0≦xi<w
0≦yi<h
テストケースの1行目には,3つの整数w,h,pが書かれている.
w,hはそれぞれグリッドの横幅と縦幅を表し,pは液体を注ぐ回数を表す.

続くh行には,それぞれw個の整数zijが書かれている. zijは(j,i)のマスの高さを表す.

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

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

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

Output

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

出典

C: 流れ - ふか杯 5th Contest | AtCoder

回答


AtCoder/fuka5_3.cpp at master · wada811/AtCoder
実は通ってない…。
Submission #17715 - ふか杯 5th Contest | AtCoder
サンプルのテストケースは通るけど他のテストケースが通らなくてわからなくて詰んだ。
というかサンプルがどうしてその結果になるの理解できなかった。
注いだ場所は高さが上がるのか…?
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)に注いだら
5 5 5 5 5
5 4 5 1 5
5 3 2 2 5
5 3 5 3 5
5 5 5 5 5
になって、ここまでで4回。そこで(2, 2)に注いだらどうなるのか。
真ん中の2より低いところがないので広がらないから出力は4なんじゃないかと思うけど5なんだよなぁ。
よくわからないので分かる人はコメントしてくれると嬉しいです。