問題一覧 > 通常問題

No.1954 CHECKER×CHECKER(2)

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : H20H20 / テスター : naskyanaskya 蜜蜂蜜蜂
1 ProblemId : 7742 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-21 00:50:41

問題文

縦 $H$ 行横 $W$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と呼ぶことにします。

各マスの色は黒か白です。

各マスの色の情報は文字列 $S_1, S_2, \ldots, S_H$ として、以下の形式で与えられます。

  • 文字列 $S_i$ の $j$ 文字目が # であればマス $(i,j)$ は黒
  • 文字列 $S_i$ の $j$ 文字目が . であればマス $(i,j)$ は白

あなたはこのマス目に対して、以下の$M$種類の操作を好きな順番で好きな回数行えます。( $0$ 回でも構いません)

$i$ 種類目の操作では、整数 $t_i$ ,$n_i$ が与えられ、以下のように色を塗り替えることが出来ることを表しています。

  • $t_i = 1$ のとき:$1 \le r \le n_i $ を満たす全ての整数 $r$ について、$r$ 行目にある全てのマスの色をそれぞれ反転させる(白色なら黒色に、黒色なら白色に塗り替える)
  • $t_i = 2$ のとき:$1 \le c \le n_i $ を満たす全ての整数 $c$ について、$c$ 列目にある全てのマスの色をそれぞれ反転させる(白色なら黒色に、黒色なら白色に塗り替える)

全てのマスについて辺で隣接しているマスの色が自身のマスの色と異なるとき、そのマス目は市松模様であるといいます。

マス目を市松模様にできるか判定してください。

入力

入力は以下の形式で標準入力から与えられる。
$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$
$M$
$t_1$ $n_1$
$t_2$ $n_2$
$\vdots$
$t_M$ $n_M$

制約

  • $2 \le H,W \le 200$
  • $S_1, S_2, \ldots , S_H$ は # または . からなる $W$ 文字の文字列
  • $0 \le M \le 23$
  • $t_i \in \{1,2\}$
  • $t_i=1$ ならば $1 \le n_i \le H$
  • $t_i=2$ ならば $1 \le n_i \le W$
  • $i \neq j$ ならば $(t_i, n_i) \neq (t_j, n_j$)
  • $H,W,M,n_i$ は整数

出力

市松模様にできるなら Yes 、そうでないなら No と出力してください。

サンプル

サンプル1
入力
3 5
.#.##
#.#..
#.#..
5
1 2
2 1
1 3
2 4
2 2
出力
Yes

例えば操作$1→2→3→4→2$のように操作すれば市松模様にできます。

サンプル2
入力
3 3
.##
#..
#..
4
1 3
1 1
2 2
2 1
出力
No
サンプル3
入力
4 5
.#.#.
#.#.#
.#.#.
#.#.#
2
1 2
2 1
出力
Yes

最初から市松模様でした。

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