The Lakes

题意翻译

给定 $n\times m$ 的矩阵,正整数上、下、左、右相连构成一个连通块。定义一个连通块的权值为该连通块中所有数的和。求矩阵中最大的连通块。 Translated by @[_JYqwq_](/user/400269)

题目描述

You are given an $ n \times m $ grid $ a $ of non-negative integers. The value $ a_{i,j} $ represents the depth of water at the $ i $ -th row and $ j $ -th column. A lake is a set of cells such that: - each cell in the set has $ a_{i,j} > 0 $ , and - there exists a path between any pair of cells in the lake by going up, down, left, or right a number of times and without stepping on a cell with $ a_{i,j} = 0 $ . The volume of a lake is the sum of depths of all the cells in the lake. Find the largest volume of a lake in the grid.

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n, m $ ( $ 1 \leq n, m \leq 1000 $ ) — the number of rows and columns of the grid, respectively. Then $ n $ lines follow each with $ m $ integers $ a_{i,j} $ ( $ 0 \leq a_{i,j} \leq 1000 $ ) — the depth of the water at each cell. It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 10^6 $ .

输出格式


For each test case, output a single integer — the largest volume of a lake in the grid.

输入输出样例

输入样例 #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