The Lakes (Codeforces 1829E)
Tags: Implement, dsu

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.

Input: 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$$$.

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


Sample Inputs:
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

Sample Outputs:
10
0
7
16
21

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline
read = lambda : [int(x) for x in readline().split()]
if __name__ == '__main__':
    for _ in range(*read()):
        (n, m) = read()
        arr = [read() for _ in range(n)]

        def bfs(i, j):
            cur = 0
            q = deque()
            q.append((i, j))
            cur += arr[i][j]
            arr[i][j] = 0
            while q:
                (x, y) = q.popleft()
                for (a, b) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= a < n and 0 <= b < m and arr[a][b]:
                        q.append((a, b))
                        cur += arr[a][b]
                        arr[a][b] = 0
            return cur
        res = 0
        for i in range(n):
            for j in range(m):
                if arr[i][j]:
                    res = max(res, bfs(i, j))
        print(res)

Solution (Python):
import sys
import os.path
from math import *
from bisect import *
from itertools import *
from collections import defaultdict as dd, Counter
from itertools import accumulate
from operator import add
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def st():
    return str(sys.stdin.buffer.readline().strip())[2:-1]

def li():
    return list(map(int, sys.stdin.buffer.readline().split()))

def mp():
    return map(int, sys.stdin.buffer.readline().split())

def inp():
    return int(sys.stdin.buffer.readline())
mod = 1000000007
INF = float('inf')

def nb(i, j, n, m, mat):
    l = []
    if i + 1 < n and mat[i + 1][j] > 0:
        l.append([i + 1, j])
    if j + 1 < m and mat[i][j + 1] > 0:
        l.append([i, j + 1])
    if i - 1 >= 0 and mat[i - 1][j] > 0:
        l.append([i - 1, j])
    if j - 1 >= 0 and mat[i][j - 1] > 0:
        l.append([i, j - 1])
    return l

def bfs(i, j, n, m, mat):
    c = mat[i][j]
    mat[i][j] = 0
    q = [[i, j]]
    while q:
        (x, y) = q.pop(0)
        neigh = nb(x, y, n, m, mat)
        for node in neigh:
            q.append([node[0], node[1]])
            c += mat[node[0]][node[1]]
            mat[node[0]][node[1]] = 0
    return c

def solve():
    (n, m) = mp()
    mat = []
    for i in range(n):
        l = li()
        mat.append(l)
    ans = 0
    for i in range(n):
        for j in range(m):
            if mat[i][j] != 0:
                s = bfs(i, j, n, m, mat)
                ans = max(ans, s)
    print(ans)
for _ in range(inp()):
    solve()

Solution (Python):
import sys, threading, os, io
import math
import time
from os import path
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
import heapq
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
from io import BytesIO, IOBase

def lcm(a, b):
    return a * b // math.gcd(a, b)
input = lambda : sys.stdin.readline().rstrip()

def lmii():
    return list(map(int, input().split()))

def ii():
    return int(input())

def si():
    return str(input())

def lmsi():
    return list(map(str, input().split()))

def mii():
    return map(int, input().split())

def msi():
    return map(str, input().split())
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
''

def solve():
    (n, m) = mii()
    arr = []
    for i in range(n):
        a = lmii()
        arr.append(a)
    dire = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    maxi = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j]:
                volume = arr[i][j]
                arr[i][j] = 0
                q = deque()
                q.append((i, j))
                while q:
                    (x, y) = q.pop()
                    for (dx, dy) in dire:
                        dx += x
                        dy += y
                        if 0 <= dx < n and 0 <= dy < m and arr[dx][dy]:
                            volume += arr[dx][dy]
                            arr[dx][dy] = 0
                            q.append((dx, dy))
                maxi = max(maxi, volume)
    print(maxi)
xxx = ii()
for _ in range(xxx):
    solve()