[Contest #4]方块切割

内存限制：256 MB 时间限制：1000 ms

有一个 $n$ 行 $m$ 列的网格，每行丛上往下一次标号为 $1,2,\dots,n$，每列从左右往右标号为 $1,2,\dots,m$，其中有些 $1 \times 1$ 的格子是障碍物。你可以横着或者竖着切 $k$ 次，每次切割必须沿着格子的边进行并且切断整个网格。

一个切 $k$ 次的切割方案可以由这样一个序列来表示 $s_1,s_2,\dots,s_k$ ($1 \le s_1 < s_2 < \dots < s_k \le n + m - 2$)。如果 $1 \le s_i \le n-1$，那么第 $i$ 次切割是沿着第 $s_i$ 行和第 $s_{i}+1$ 行之间的边切割的；如果 $n \le s_i \le n + m - 2$，那么第 $i$ 次切割是沿着第 $s_i-n+1$ 列和第 $s_{i}-n+2$ 列之间的边切割的。

不妨假设你横着切了 $a$ 次，竖着切了 $b=k-a$ 次，那么总共会有 $(a+1) \times (b+1)$ 个小网格。请你求出一种切割方案，使得每个小网格里面非障碍物格子数目一样。如果有多种切割方案，请输出一个字典序最小的切割方案。

输入有多组数据。第一行有一个整数 $T$，表示测试数据组数。然后对于每组数据：

第一行有 $3$ 个正整数 $n$，$m$ 和 $k$ ($2 \le n, m \le 1000, 1 \le k \le n + m - 2$)，表示网格行数，列数和切割次数。

接下来 $n$ 行，每行包含长度为 $m$ 的 $01$ 串。如果第 $i$ 行的第 $j$ 个字符是 $1$ 表示第 $i$ 行第 $j$ 列格子是障碍物，否则是非障碍物。

保证所有数据里 $n \times m$ 的和不超过 $10^6$。

对于每组数据，如果不存在这样一种切法，输出 "Impossible"，否则输出一个字典序最小的切割方案。

样例输入 1

样例输出 1

1
1 2
Impossible

C1075 [Contest #4]方块切割

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示