黑白翻转棋(Lights Out)

题目描述

有一种叫做黑白翻转棋的游戏，棋盘由 $n\times m$ 个方格组成，每个方格上放置一枚棋子，每一枚棋子一面为黑，一面为白。若翻转某枚棋子，它的颜色就会由黑变白，或者由白变黑。一开始，棋子可能是黑色的，也可能是白色的。如果把所有的格子都翻成白色，游戏就结束了。

小爱可以按照任意顺序翻转任意数量的棋子，但游戏规则规定，选择翻动某一枚棋子时，与这个棋子的方格共享边界的其它棋子也必须被同时被翻转。小爱可能在一个步骤中，同时翻转五个棋子（棋子在中间）、四个棋子（棋子在边界上）或三个棋子（当棋子在角上）。

请帮助小爱计算一下，她最少需要多少步骤才能把所有棋子都翻成白色？如果给定的初始局面是不可能结束游戏的，输出 Impossible。

输入格式

• 第一行：两个整数 $n$ 和 $m$；
• 第二行到 $n+1$ 行：第 $i+1$ 行有 $m$ 个整数表示初始棋盘中第 $i$ 行棋子的颜色，1 表示黑色，0 表示白色。

输出格式

如果不能将所有棋子都翻转为白面朝上的话，输出 Impossible。

否则输出最少翻转次数。

样例输入 #1

3 3
0 1 0
1 1 1
0 1 0

样例输出 #1

1

说明：翻转中间一个棋子即可。

数据范围

• 对于 $30\%$ 的数据，$1\le n,m\le 4$；
• 对于 $60\%$ 的数据，$1\le n,m\le 10$；
• 对于 $100\%$ 的数据，$1\le n,m\le 20$。

知识点与难度

本题涉及的知识点从属于 GESP 六级（枚举、位运算、状态搜索），难度等级：⭐⭐⭐⭐。

测试点分布