No.923 Othello Kirikizamu-tan
lumc_
Lemma299
polylogKIf you are experiencing an issue where math formulas are not displayed, please take the following measures.
https://twitter.com/yukicoder/status/1191757446596812800?s=20
Problem Statement
Kiritan and Una-chan played a special game of Othello on a board made of equally sized square cells arranged in $H$ cells vertically and $W$ cells horizontally.
Now, all cells are filled with white or black stones (exactly $1$ stone is placed on each cell), and the game has been decided.
The color of the stone placed on the cell that is $i$-th from the top and $j$-th from the left is represented by $A_{ij}$: a black stone is placed if it is $0$, and a white stone is placed if it is $1$.
Kiritan wants to play further with this Othello board. So she decided to cut the Othello board into smaller pieces.
Precisely, she repeats the following sequence of operations until no more operations can be performed.
- $1$. Choose $1$ board with $2$ or more cells.
- $2$. Cut the chosen board along a line perpendicular to one of its edges. However, it must not be cut through the middle of an edge or a cell. This creates $2$ new boards.
- $3$. Freely choose one of the $2$ newly created boards, and flip all stones on the chosen board. Here, flipping a stone means replacing a white stone with a black stone and a black stone with a white stone.
The operations end when every board consists of $1$ cell.
Kiritan wants all stones to be white in the end. Determine whether this is possible.
Input
$H \; W \\
A_{11}A_{12}\cdots A_{1W} \\
A_{21}A_{22}\cdots A_{2W} \\
\vdots \\
A_{H1}A_{H2}\cdots A_{HW}$
- $2 \le \color{red}{H \times W} \le 10^5$
- $1 \le H, W$
- $A_{ij} = 0, 1$ ($0$ represents a black stone, and $1$ represents a white stone.)
- There are no spaces between the values in the same row of $A$ in the input.
- All inputs are integers.
Output
Print YES if all stones can be made white, and NO otherwise, followed by a newline.
Sample
Sample 1
Input
3 2 00 10 01
Output
YES
For example, this can be achieved by the following procedure (| and - indicate the cuts).
1. Cut the initial board at the following position and flip the right part.
0|1 1|1 0|0
2. Cut the left board at the following position and flip the upper part.
1|1 -|1 1|0 0|
3. Cut the right board at the following position and flip the lower part.
1|1 -|- 1|0 0|1
4. Cut the lower-left board at the following position and flip the lower part.
1|1 -|- 1|0 -|1 1|
4. Cut the lower-right board at the following position and flip the upper part.
1|1 -|- 1|1 -|- 1|1
Sample 2
Input
2 2 11 11
Output
NO
Kiritan seems dissatisfied with the board being all white from the start.
Sample 3
Input
8 8 00000000 00000000 01000000 01000000 00110000 01010000 00101100 00000000
Output
NO
It seems Kiritan and Una-chan played regular Othello.
Sample 4
Input
5 1 1 0 1 0 1
Output
YES
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。