No.307 最近色塗る問題多くない?

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 57
作問者 : koyumeishikoyumeishi
3 ProblemId : 769 / 出題時の順位表

問題文

縦$H$マス、横$W$マスの方眼紙のマスを2色のインクで塗りつぶすことを考えます。

上から数えて$R$行目、左から数えて$C$列目のマスを$(R,C)$と表記します。 一番左上は$(1,1)$、一番右下は$(H,W)$です。
マス$(R,C)$ははじめ、色$A_{R,C}$で塗られています。

あるマス$(R,C)$と、それに隣接するマス$(R^\prime,C^\prime)$は、2つのマスが同色であるとき、 「$(R,C)$と$(R^\prime,C^\prime)$は連結である」とします。
また、$(R,C)$と$(R^\prime,C^\prime)$が連結で、かつ、$(R^\prime,C^\prime)$と$(R^{\prime\prime},C^{\prime\prime})$が連結であるとき、 $(R,C)$と$(R^{\prime\prime},C^{\prime\prime})$も連結であるとします。
ここで「隣接する」とは、$(R,C)$と$(R^\prime,C^\prime)$の マンハッタン距離が$1$ である場合、 即ち$(R^\prime,C^\prime)$ が $(R+1,C), (R-1,C), (R,C+1), (R,C-1)$のいずれかである場合を指します。

「マス$(R,C)$と連結である全てのマスを 色$X$ で塗りつぶす」というクエリが$Q$個与えられます。
$Q$回の塗りつぶしを終えた後の方眼紙の各マスの色を出力してください。

要するにペイントソフトの「塗りつぶし」機能です。

入力

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$
$Q$
$R_1$ $C_1$ $X_1$
$\vdots$
$R_Q$ $C_Q$ $X_Q$

入力は全て整数で与えられ、以下の制約を満たします。
$1 \leq H,W \leq 200$
$1 \leq Q \leq 5 \times 10^4$
$0 \leq A_{R,C}, X_i \leq 1$
$1 \leq R_i \leq H$
$1 \leq C_i \leq W$

出力

$A^\prime_{1,1}$ $A^\prime_{1,2}$ $\dots$ $A^\prime_{1,W}$
$\vdots$
$A^\prime_{H,1}$ $A^\prime_{H,2}$ $\dots$ $A^\prime_{H,W}$

塗りつぶした後の各マスの色$A^\prime_{R,C}$を出力してください。

サンプル

サンプル1
入力
3 3
0 1 0
1 0 1
0 1 0
1
2 2 1
出力
0 1 0
1 1 1
0 1 0

サンプル2
入力
4 4
0 0 1 0
1 1 0 1
0 1 0 0
1 1 1 1
2
3 3 1
2 1 0
出力
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

ここが

0 0 1 0
1 1 * 1
0 1 * *
1 1 1 1
こうなって
0 0 1 0
1 1 1 1
0 1 1 1
1 1 1 1
ここが
0 0 * 0
* * * *
0 * * *
* * * *
こうじゃ
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

サンプル3
入力
5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
3
1 1 1
2 2 1
3 3 1
出力
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

サンプル4
入力
5 3
1 0 1
0 0 1
1 1 0
1 0 1
1 0 1
3
1 1 0
4 3 1
5 3 0
出力
0 0 1
0 0 1
1 1 0
1 0 0
1 0 0

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。