← 返回题目列表

Codeforces · 1829/E

E. 湖泊

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

给你一个 $$$n \times m$$$ 个非负整数网格 $$$a$$$。值 $$$a_{i,j}$$$ 表示第 $$$i$$$ 行和第 $$$j$$$ 列的水深。

湖泊是一组单元格,使得:

- 集合中的每个单元格都有 $$$a_{i,j} > 0$$$,并且
- 湖中任意一对单元格之间都存在一条路径,只需向上、向下、向左或向右多次,并且不踩到 $$$a_{i,j} = 0$$$ 的单元格。

湖泊的体积是湖泊中所有单元的深度总和。

找出网格中湖泊的最大体积。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) - 分别是网格的行数和列数。

然后 $$$n$$$ 行后面各有 $$$m$$$ 整数 $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1000$$$) - 每个单元格的水深。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出一个整数 - 网格中湖泊的最大体积。

示例

输入 #1

5
3 3
1 2 0
3 4 0
0 0 5
1 1
0
3 3
0 1 1
1 0 1
1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 0 5 0 1
1 0 0 0 1
1 1 1 1 1
5 5
1 1 1 1 1
1 0 0 0 1
1 1 4 0 1
1 0 0 0 1
1 1 1 1 1

输出 #1

10
0
7
16
21