给你一个二进制网格$$$^{\text{*}}$$$ $$$G$$$,维度为$$$n \times m$$$。
让我们定义一个 矩形 作为元组 $$$(u,d,l,r)$$$ 满足以下条件:
- $$$1 \le \boldsymbol{u \lt d} \le n$$$;
- $$$1 \le \boldsymbol{l \lt r} \le m$$$;
- 单元格 $$$(u,l)$$$、$$$(u,r)$$$、$$$(d,l)$$$、$$$(d,r)$$$ 均包含 $$$1$$$。
然后, 区域 矩形 $$$(u,d,l,r)$$$ 的 定义为 $$$(d-u+1) \cdot (r-l+1)$$$。
例如,考虑下面给出的二进制网格。
$$\begin{矩阵} 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{矩阵}$$
在这里,您可能会看到两个矩形 $$$(1,2,1,3)$$$ 和 $$$(1,3,3,5)$$$$$$^{\text{†}}$$$,每个矩形的面积分别为 $$$6$$$ 和 $$$9$$$。
对于每个单元格 $$$(i,j)$$$,找到 最小面积 任何矩形 $$$(u,d,l,r)$$$ 使得 $$$u \le i \le d$$$ 和 $$$l \le j \le r$$$。
$$$^{\text{*}}$$$二元网格是每个单元格包含 $$$0$$$ 或 $$$1$$$ 的网格。第 $$$i$$$ 行第 $$$j$$$ 列上的单元格表示为单元格 $$$(i,j)$$$。
$$$^{\text{†}}$$$请注意,这些是网格中唯一的矩形;例如,$$$(1,1,1,5)$$$ 是 不 一个矩形,因为它不满足 $$$u \lt 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,d,l,r)$$$ 使得 $$$u \le i \le d$$$ 和 $$$l \le j \le r$$$,输出任何这样的矩形的最小面积;
- 否则,输出$$$0$$$。
示例
输入复制
33 51010110100001014 60111010100011000101011105 51110010110111110110100111
输出复制
6 6 6 9 96 6 6 9 90 0 9 9 90 10 8 8 10 100 10 8 8 10 1010 10 8 8 10 010 10 8 8 10 06 6 6 0 06 6 4 4 06 4 4 4 60 4 4 6 60 0 6 6 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$$$。