General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
240657725 Practice:
vivekj.joshi9
1829E - 19 PyPy 3-64 Accepted 888 ms 29480 KB 2024-01-07 11:21:43 2024-01-07 11:21:43
→ Source
from typing import List
from collections import deque
import sys

def get_connected_nodes_sum(mat: List[List[int]], n, m):

    queue = deque([(n, m)])
    node_sum = 0

    while queue:
        i, j = queue.popleft()

        if mat[i][j] == 0:
            continue

        node_sum += mat[i][j]
        mat[i][j] = 0

        if i - 1 >= 0 and mat[i - 1][j] != 0:
            queue.append((i - 1, j))

        if i + 1 < (len(mat)) and mat[i + 1][j] != 0:
            queue.append((i + 1, j))

        if j - 1 >= 0 and mat[i][j - 1] != 0:
            queue.append((i, j - 1))

        if j + 1 < len(mat[0]) and mat[i][j + 1] != 0:
            queue.append((i, j + 1))

    return node_sum


def solve(mat: List[List[int]], n: int, m: int) -> int:

    max_sum = 0
    for i in range(n):
        for j in range(m):
            if mat[i][j] != 0:
                max_sum = max(max_sum, get_connected_nodes_sum(mat, i, j))

    return max_sum


t = int(sys.stdin.readline())

for _ in range(t):
    n, m = list(map(int, sys.stdin.readline().split(' ')))
    mat = []
    for i in range(n):
        mat.append(list(map(int, sys.stdin.readline().split(' '))))
    sys.stdout.write(str(solve(mat, n, m)) + '\n')
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details