No.1954 CHECKER×CHECKER(2)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
H20
蜜蜂
naskya