AOJ 1308 : Awkward Lights
Awkward Lights | Aizu Online Judge
問題概要
- N*Mのマスがあります。
- 各マスにはライトが設置されており 1 がON、 0 がOFFです。
- あるマスのスイッチを押すとそのマスのライトとそのマスとマンハッタン距離がDであるようなマスのライトのON/OFFが反転します。
- マスをいくつか押して全てのマスをOFFに出来るか判定してください。
解法
- 既にONのマスにについて、そのマスが影響を受けるマスのうち押すマスの合計が奇数のときOK
- 既にOFFのマスにについて、そのマスが影響を受けるマスのうち押すマスの合計が偶数のときOK
- というのを各マスについて見ていくと
連立方程式がたくさんできる。
例）
a + b + c = 1 ( mod 2 )
a + c + d + e = 0 ( mod 2 )
b + c + d + f = 1 ( mod 2 )
c + d + e + f = 1 ( mod 2 )
e + f = 1 ( mod 2 ) - modの連立方程式の解があるかどうかをガウスジョルダンで判定。
- ガウスジョルダンの際に、『解なし』か『解複数』のどちらかを判定するために打ち切らず
値を当てはめた時に式が成り立つかをチェックして判定する。
ソースコード
感想
はるか昔、解けずに途中まで考察して終わっていた問題。
