← 返回题目列表

Codeforces · 2159/B

B. 矩形

中文机器翻译题面 查看原题

给你一个二进制网格$$$^{\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$$$。

示例

输入
复制

3
3 5
10101
10100
00101
4 6
011101
010001
100010
101110
5 5
11100
10110
11111
01101
00111

输出
复制

6 6 6 9 9
6 6 6 9 9
0 0 9 9 9
0 10 8 8 10 10
0 10 8 8 10 10
10 10 8 8 10 0
10 10 8 8 10 0
6 6 6 0 0
6 6 4 4 0
6 4 4 4 6
0 4 4 6 6
0 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$$$。