CF2159B Rectangles

给定一个二进制网格 $G$，其尺寸为 $n \times m$。 我们将一个矩形定义为元组 $(u,d,l,r)$，需满足以下条件： - $1 \le u < d \le n$； - $1 \le l < r \le m$； - 单元格 $(u,l)$、$(u,r)$、$(d,l)$、$(d,r)$ 均为 $1$。 矩形 $(u,d,l,r)$ 的面积定义为 $(d-u+1) \cdot (r-l+1)$。 例如，考虑如下二进制网格： $$ \begin{matrix} 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{matrix} $$ 在这里，你可以得到两个矩形 $(1,2,1,3)$ 和 $(1,3,3,5)$，它们的面积分别为 $6$ 和 $9$。 对于每个单元格 $(i,j)$，请找到所有满足 $u \le i \le d$ 且 $l \le j \le r$ 的矩形 $(u,d,l,r)$ 中面积的最小值。 如果不存在这样的矩形，则输出 $0$。 注：一个二进制网格是指每个单元格只包含 $0$ 或 $1$。第 $i$ 行第 $j$ 列的单元格记作 $(i,j)$。 注意，这些例子中只存在上述两个矩形。例如，$(1,1,1,5)$ 不是矩形，因为 $u < d$ 不满足。

每组测试数据包含多个测试用例。第一行为整数 $t$（$1 \le t \le 10^4$），表示测试用例组数。 每一组测试数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n,m$，$n\cdot m \le 250\,000$）。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示 $G$ 的第 $i$ 行（$G_{i,j} \in \{0,1\}$）。 保证所有测试用例的 $n \cdot m$ 总和不超过 $250\,000$。

对于每组测试用例，输出一个 $n$ 行 $m$ 列的网格。对于第 $i$ 行第 $j$ 列，若存在至少一个满足 $u \le i \le d$ 且 $l \le j \le r$ 的矩形 $(u,d,l,r)$，请输出所有此类矩形的最小面积；否则输出 $0$。

第一个测试用例的讲解见题面。 对于第三个测试用例，共有 $6$ 个面积最小的覆盖至少一个单元格的矩形： - $(1,3,1,2)$ ，面积为 $6$； - $(1,2,1,3)$ ，面积为 $6$； - $(3,4,2,3)$ ，面积为 $4$； - $(2,3,3,4)$ ，面积为 $4$； - $(3,5,4,5)$ ，面积为 $6$； - $(4,5,3,5)$ ，面积为 $6$。 由 ChatGPT 5 翻译