题目描述

给定一个 $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$。

输出格式

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

样例

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

10
0
7
16
21

样例说明

由 ChatGPT 4.1 翻译

来源

Codeforces 1829E，英文题名 The Lakes。