G - 4x4 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N\times N 整数行列 A が与えられます。以下の条件を満たす N \times N 整数行列 B が存在するか判定してください。

  • すべての整数対 (i,j) について、 A_{i,j} \neq -1 ならば A_{i,j}=B_{i,j}
  • B のどの 4 \times 4 の部分正方形を取り出しても、その部分正方形は 1 以上 16 以下の整数をすべて含む。

制約

  • 4 \le N \le 500
  • A_{i,j}=-1 または 1 \le A_{i,j} \le 16
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

出力

条件を満たす B が存在しないならば No を、存在するならば Yes を出力せよ。

入力例 1

4
1 2 -1 -1
5 -1 7 -1
9 10 -1 -1
13 14 15 -1

出力例 1

Yes

入力例 2

5
1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 1 -1
-1 -1 -1 -1 -1

出力例 2

No

入力例 3

6
1 -1 -1 -1 -1 1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1

出力例 3

No