No.460 Front-and-Back Chiwaawa
レベル :
/ AI推定難易度 : 1400
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 :
hirakich1048576
/ テスター :
kroton
タグ : / 解いたユーザー数 65
作問者 :
hirakich1048576
/ テスター :
問題文最終更新日: 2026-06-25 12:46:49
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Advent Calendar Contest 2016
(順位表)
の他の問題:
Problem Statement
Chiwawa is a math genius, but has recently been feeling a decline.
Thinking that things could not go on like this, Chiwawa decided to solve a certain puzzle every morning.
- The board has M cells vertically × N cells horizontally.
- Each cell is white on its front and black on its back, and in the initial state some of the cells are flipped over.
- When you flip a cell, the surrounding cells in its 8-neighborhood are flipped along with it.
(For a cell on the edge, only the surrounding cells that can be flipped are affected.) - The goal of this game is to turn all the cells front side up in the minimum number of moves.
Find the minimum number of moves needed to turn all the cells front side up.
If no such sequence of moves exists, print "Impossible".
Input
M N
\(\begin{array}{cccc}
a_{ 1,1 } & a_{ 1,2 } & \ldots & a_{ 1,N } \\
a_{ 2,1 } & a_{ 2,2 } & \ldots & a_{ 2,N } \\
\vdots & \vdots & \ddots & \vdots \\
a_{ M,1 } & a_{ M,2 } & \ldots & a_{ M,N }
\end{array}\)
\(a_{ i,j }\) refers to the cell in row \(i\), column \(j\) of the board, and is 0 if the cell is front side up and 1 if it is back side up.
\( 1 \leq M,N \leq 8 \)
Output
If a number of moves that flips all the cells exists, print the minimum number of moves; if it does not exist, print "Impossible".
Sample
Sample 1
Input
5 5 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 0
Output
2
Flipping the 2 cells at row 4, column 2 and row 2, column 4 is the shortest sequence of moves.
Sample 2
Input
4 4 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
Output
16
Sample 3
Input
8 5 0 0 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1
Output
5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。