1829E.md (1525B)
1 Source: https://codeforces.com/problemset/problem/1829/E 2 3 E. The Lakes 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 A lake is a set of cells such that: 24 25 * each cell in the set has $a_{i,j} \gt 0$, and 26 * 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$. 27 28 The volume of a lake is the sum of depths of all the cells in the lake. 29 30 Find the largest volume of a lake in the grid. 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 35 36 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. 37 38 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. 39 40 It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$. 41 42 Output 43 44 For each test case, output a single integer — the largest volume of a lake in the grid. 45 46 Example 47 48 Input 49 50 ``` 51 5 52 53 3 3 54 55 1 2 0 56 57 3 4 0 58 59 0 0 5 60 61 1 1 62 63 0 64 65 3 3 66 67 0 1 1 68 69 1 0 1 70 71 1 1 1 72 73 5 5 74 75 1 1 1 1 1 76 77 1 0 0 0 1 78 79 1 0 5 0 1 80 81 1 0 0 0 1 82 83 1 1 1 1 1 84 85 5 5 86 87 1 1 1 1 1 88 89 1 0 0 0 1 90 91 1 1 4 0 1 92 93 1 0 0 0 1 94 95 1 1 1 1 1 96 ``` 97 98 Output 99 100 ``` 101 10 102 0 103 7 104 16 105 21 106 ```