問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : koyumeishikoyumeishi
6 ProblemId : 769 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-27 10:13:31

問題文

縦$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。