P13264 [GCJ 2014 Finals] Checkerboard Matrix

当感到无聊时，Mija 有时会玩一个关于矩阵的游戏。她尝试用尽可能少的操作次数将一个矩阵变换成另一个矩阵。对 Mija 来说，一次操作是指交换任意两行，或交换任意两列。 今天，Mija 有一个特别的矩阵 $\mathbf{M}$。这是一个 $2\mathbf{N} \times 2\mathbf{N}$ 的矩阵，其中每个元素都是 $0$ 或 $1$。Mija 决定尝试将 $\mathbf{M}$ 转换成一个**棋盘矩阵**，即矩阵中每一行与每一列的元素都按照 $0$ 和 $1$ 交替出现。 你能帮助 Mija 找出将 $\mathbf{M}$ 转换为棋盘矩阵所需的**最少交换次数**吗？如果无法转换成棋盘矩阵，请输出 `"IMPOSSIBLE"`。

第一行是测试用例数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。 每个测试用例的第一行包含一个整数 $\mathbf{N}$。接下来的 $2\mathbf{N}$ 行，每行包含 $2\mathbf{N}$ 个字符（仅由 `'0'` 和 `'1'` 组成），表示矩阵 $\mathbf{M}$ 的一行。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最少的行交换与列交换次数之和；若无法转换成棋盘矩阵，输出 `"IMPOSSIBLE"`。

**样例解释** - 样例 1 中，矩阵本身已经是棋盘矩阵，无需任何操作。 - 样例 2 中，Mija 可以先交换第 1 列和第 2 列，再交换第 1 行和第 2 行，即可得到棋盘矩阵，总共 2 次操作。 - 样例 3 中，矩阵中的 $1$ 数量不够，无法排成棋盘矩阵，因而输出为 `"IMPOSSIBLE"`。 ## 限制条件 - $1 \leq \mathbf{T} \leq 100$ ### Small 数据集（4 分） - 时间限制：~~60~~ 3 秒 - $1 \leq \mathbf{N} \leq 10$ ### Large 数据集（9 分） - 时间限制：~~120~~ 5 秒 - $1 \leq \mathbf{N} \leq 10^3$ 翻译由 ChatGPT-4o 完成