No.1056 2D Lamps

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 20
作問者 : QCFiumQCFium / テスター : noshi91noshi91
3 ProblemId : 3469 / 出題時の順位表
問題文最終更新日: 2020-05-15 22:30:23

問題文

この問題の実行時間制限は3sであり、C++以外での正解が困難な可能性があります。入出力はscanf/printfを使うことを推奨します。

$N$行$N$列の格子状に$N^2$個のランプが配置されています。
上から$i$行目、左から$j$列目のランプをランプ$(i,j)$と呼ぶことにします。
$N^2$個のランプの状態を表す盤面が$M$個与えられ、$A_{i,j,k}$が#なら$i$個目の盤面のランプ$(j,k)$が点灯していて、.なら消灯しています。
$1 \le i \lt j \le M$を満たす全ての$i,j$について、$A_i$の盤面から始めて以下に従って$A_j$の盤面を作ることができるかを判定してください。

あなたは、整数$k$を選んで以下のいずれかを選んで実行するということを、0回以上の任意の回数できます。

  • $i=k$となるようなランプ$(i,j)$全てについて、点灯しているなら消灯し、そうでないなら点灯する。
  • $j=k$となるようなランプ$(i,j)$全てについて、点灯しているなら消灯し、そうでないなら点灯する。
  • $i+j=k$となるようなランプ$(i,j)$全てについて、点灯しているなら消灯し、そうでないなら点灯する。
  • $i-j=k$となるようなランプ$(i,j)$全てについて、点灯しているなら消灯し、そうでないなら点灯する。

入力

$N\ M$
$A_{1,1,1}A_{1,1,2}A_{1,1,3}\dots A_{1,1,N}$
$A_{1,2,1}A_{1,2,2}A_{1,2,3}\dots A_{1,2,N}$
$A_{1,3,1}A_{1,3,2}A_{1,3,3}\dots A_{1,3,N}$
$\hspace{55pt} \vdots$
$A_{1,N,1}A_{1,N,2}A_{1,N,3}\dots A_{1,N,N}$

$A_{2,1,1}A_{2,1,2}A_{2,1,3}\dots A_{2,1,N}$
$A_{2,2,1}A_{2,2,2}A_{2,2,3}\dots A_{2,2,N}$
$A_{2,3,1}A_{2,3,2}A_{2,3,3}\dots A_{2,3,N}$
$\hspace{55pt} \vdots$
$A_{2,N,1}A_{2,N,2}A_{2,N,3}\dots A_{2,N,N}$

$\hspace{60pt} \vdots$

$A_{M,1,1}A_{M,1,2}A_{M,1,3}\dots A_{M,1,N}$
$A_{M,2,1}A_{M,2,2}A_{M,2,3}\dots A_{M,2,N}$
$A_{M,3,1}A_{M,3,2}A_{M,3,3}\dots A_{M,3,N}$
$\hspace{55pt} \vdots$
$A_{M,N,1}A_{M,N,2}A_{M,N,3}\dots A_{M,N,N}$

$1 \le N \le 200$
$2 \le M \le 200$
$N,M$は整数
$A_{i,j,k}$は#又は.である

出力

以下の形式に従って出力してください。

$B_{1,2}B_{1,3}B_{1,4}B_{1,5}\dots B_{1,M}$
$B_{2,3}B_{2,4}B_{2,5}\dots B_{2,M}$
$B_{3,4}B_{3,5}\dots B_{3,M}$
$\hspace{17pt} \vdots$
$B_{M - 1,M}$
$B_{i,j}$は$A_i$の盤面から$A_j$を作れる場合1、そうでない場合0でなければなりません。
最後には改行を入れてください。つまり合計でちょうど$M - 1$個の改行を出力してください。(2020/05/15 22:29 追記)

サンプル

サンプル1
入力
5 3
.....
.....
.....
.....
.....

....#
...#.
..#..
.#...
#....

#.##.
#..##
.#.#.
...#.
.#...
出力
10
0

盤面1から盤面2を作り出すのは「$i+j=6$となるようなランプについて反転」をすることで可能です。
盤面1から盤面3, 盤面2から盤面3はどうやっても作ることが出来ません。

サンプル2
入力
4 6
.#..
.#.#
#.##
.#.#

.###
##..
###.
##..

.#..
#...
.#..
###.

#..#
.##.
####
.#.#

#.##
..#.
###.
....

##.#
##..
#.##
.#..
出力
10101
0101
010
01
0

サンプル3
入力
1 2
.

#
出力
1

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