問題一覧 > 通常問題

No.923 オセロきりきざむたん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 : lumc_lumc_ / テスター : Lemma299Lemma299 polylogKpolylogK
3 ProblemId : 3451 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-11-08 19:59:58

数式が表示されない不具合が発生している場合は次の対応をお願いします.

https://twitter.com/yukicoder/status/1191757446596812800?s=20

問題文

きりたんとウナちゃんは,大きさの等しい正方形のマスが縦 $H$ マス,横 $W$ マスに敷き詰められた盤からなる特殊なオセロで遊びました.
いま,すべてのマスが白色または黒色の石で埋まり(各マスについて丁度 $1$ つの石が置かれています),決着が付きました.
上から $i$ 番目,左から $j$ 番目のマスに置かれている石の色は $A_{ij}$ で表され,$0$ のとき黒色の石が,$1$ のとき白色の石が置かれています.
きりたんは,このオセロの盤面で更に遊びたいと考えました.そこで,オセロの盤を小さく切ることにしました.
正確には,以下の一通りの操作を操作が出来なくなるまで行います.

  • $1$. マスの数が $2$ 以上の盤を $1$ つ選ぶ.
  • $2$. 選んだ盤のある辺に垂直な線に沿って選んだ盤を切断する.ただし,辺やマスの途中を切断したりはしない.これにより新たに $2$ つの盤ができる.
  • $3$. 新たに出来た $2$ つの盤から片方を自由に選び,その選んだ盤のすべての石を反転する.ここで石を反転するとは,白色の石を黒色の石に,黒色の石を白色の石に置き換えることを指す.

すべての盤が $1$ マスからなる盤になったとき,操作が終了します.
きりたんは,最終的にすべての石が白になるようにしたいです.それが可能かどうか判定してください.

入力

$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$ は黒色の石,$1$ は白色の石を表します.)
  • $A$ の同じ行の入力の間に空白はありません.
  • 入力はすべて整数.

出力

すべて石を白色に出来る時 YES を,そうでない時 NO を出力し,改行してください.

サンプル

サンプル1
入力
3 2
00
10
01
出力
YES

例えば,以下のような手順で達成できます(| および - で分割を示す).

1. はじめの盤を次の位置で分割し右側を反転する.

0|1
1|1
0|0

2. 左側の盤を次の位置で分割し,上側を反転する.

1|1
-|1
1|0
0|

3. 右側の盤を次の位置で分割し,下側を反転する.

1|1
-|-
1|0
0|1

4. 左下の盤を次の位置で分割し,下側を反転する.

1|1
-|-
1|0
-|1
1|

4. 右下の盤を次の位置で分割し,上側を反転する.

1|1
-|-
1|1
-|-
1|1
サンプル2
入力
2 2
11
11
出力
NO

きりたんははじめから真っ白では不服のようです.

サンプル3
入力
8 8
00000000
00000000
01000000
01000000
00110000
01010000
00101100
00000000
出力
NO

きりたんとウナちゃんは通常のオセロをやったみたいです.

サンプル4
入力
5 1
1
0
1
0
1
出力
YES

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