← Home
write a go solution for Description:
You are given an nxm 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.

Input Format:
The first line contains a single integer t (1<=qt<=q10^4) — the number of test cases.

The first line of each test case contains two integers n,m (1<=n,m<=1000) — the number of rows and columns of the grid, respectively.

Then n lines follow each with m integers a_i,j (0<=a_i,j<=1000) — the depth of the water at each cell.

It is guaranteed that the sum of n*m over all test cases does not exceed 10^6.

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

Note:
None. Output only the code with no comments, explanation, or additional text.