牛可乐的翻转游戏
题号:NC235250
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

牛可乐发明了一种新型的翻转游戏!

在一个有 nm 列的棋盘上,每个格子摆放有一枚棋子,每一枚棋子的颜色要么是黑色,要么是白色。每次操作牛可乐可以选择一枚棋子,将它的颜色翻转(黑变白,白变黑),同时将这枚棋子上下左右相邻的四枚棋子的颜色翻转(如果对应位置有棋子的话)。

牛可乐想请你帮他判断一下,能否通过多次操作将所有棋子都变成黑色或者白色?如果可以,最小操作次数又是多少呢?

输入描述:

第一行两个整数 ,代表棋盘的行数和列数。

之后 n 行,每行 m 个数字,第 i 个数字如果为 0 ,代表对应位置的棋子为白色,如果为 1 则为黑色。

输出描述:

如果无法将所有棋子变成一个颜色,输出 "Impossible"(不含引号),否则输出变成一个颜色的最小操作次数。
示例1

输入

复制
4 4
1001
1101
1001
1000

输出

复制
4