問題一覧 > 通常問題

No.1954 CHECKER×CHECKER(2)

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 48
作問者 : H20 / テスター : 蜜蜂 naskya
お気に入りにしたユーザー ProblemId : 7742 / 自分の提出
問題文最終更新日: 2022-05-21 00:50:41
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 344 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called cell $(i,j)$.

Each cell is colored either black or white.

The colors of the cells are given as strings $S_1, S_2, \ldots, S_H$ in the following format.

  • If the $j$-th character of the string $S_i$ is #, cell $(i,j)$ is black.
  • If the $j$-th character of the string $S_i$ is ., cell $(i,j)$ is white.

You may perform the following $M$ types of operations on this grid in any order and any number of times (possibly $0$ times).

For the $i$-th type of operation, integers $t_i$ ,$n_i$ are given, which indicate that colors can be repainted as follows.

  • If $t_i = 1$: for every integer $r$ satisfying $1 \le r \le n_i $, invert the color of every cell in row $r$ (white is repainted black, and black is repainted white).
  • If $t_i = 2$: for every integer $c$ satisfying $1 \le c \le n_i $, invert the color of every cell in column $c$ (white is repainted black, and black is repainted white).

The grid is called a checkered pattern if, for every cell, the cells adjacent to it by an edge have a color different from that cell's own color.

Determine whether the grid can be made into a checkered pattern.

Input

The input is given from Standard Input in the following format.
$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$
$M$
$t_1$ $n_1$
$t_2$ $n_2$
$\vdots$
$t_M$ $n_M$

Constraints

  • $2 \le H,W \le 200$
  • $S_1, S_2, \ldots , S_H$ are strings of length $W$ consisting of # or .
  • $0 \le M \le 23$
  • $t_i \in \{1,2\}$
  • If $t_i=1$, then $1 \le n_i \le H$
  • If $t_i=2$, then $1 \le n_i \le W$
  • If $i \neq j$, then $(t_i, n_i) \neq (t_j, n_j$)
  • $H,W,M,n_i$ are integers

Output

If the grid can be made into a checkered pattern, print Yes; otherwise, print No.

Sample

Sample 1
Input
3 5
.#.##
#.#..
#.#..
5
1 2
2 1
1 3
2 4
2 2
Output
Yes

For example, performing the operations in the order $1→2→3→4→2$ makes the grid a checkered pattern.

Sample 2
Input
3 3
.##
#..
#..
4
1 3
1 1
2 2
2 1
Output
No
Sample 3
Input
4 5
.#.#.
#.#.#
.#.#.
#.#.#
2
1 2
2 1
Output
Yes

The grid is a checkered pattern from the start.

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