codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```