2385 - oaste

Pe un continent reprezentat printr-o matrice cu n linii și m coloane se află mai multe state, toate în conflict. Astfel, fiecare si-a mobilizat oastea.

Fiecare element al matricei memorează câte o cifră. Două elemente învecinate pe linie sau pe coloană (nu si pe diagonală) aparțin aceluiași stat și se numesc regiuni.

O poziție (i,j) a unei regiuni din matrice este dată de indicele i de linie și indicele j coloană al elementului din matrice corespunzător acestei regiuni.

O poziție din matrice ce contine cifra 0 este o regiune neutră si nu are soldați, iar poziția ce conține o cifră c nenulă este o regiune ce aparține unui stat și are c soldați.

Cerința

Să se determine numărul maxim de soldați dintr-o regiune a statului care are cei mai mulți soldați, precum și poziția acestei regiuni în matrice (linia și coloana).

Date de intrare

Fișierul de intrare oaste.in conține pe prima linie numerele naturale n si m, iar pe fiecare dintre următoarele n linii conține câte m cifre, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire oaste.out va conține pe prima linie trei numere separate prin cate un spațiu, reprezentând numărul maxim de soldați dintr-o regiune a statului care are cei mai mulți soldați, respectiv linia și coloana poziției acestei regiuni in matrice.

Restricții și precizări

• n si m vor fi numere naturale cu valori intre 1 si 100 inclusiv;
• fiecare element al matricei va avea valori naturale cuprinse intre 0 si 9 inclusiv;
• există cel puțin o cifră nenula în matrice
• spunem ca un stat are coordonatele (i,j) în matrice dacă regiunea din poziția (i,j) aparține acestui stat și este regiunea cu cea mai mică poziție în sens lexicografic dintre regiunile statului.
• perechea (i,j) este mai mică în sens lexicografic ca perechea (x,y) dacă i<x sau dacă i=x și j<y
• dacă există două state cu același număr de soldați și același număr maxim de soldați într-o regiune, se va lua în considerare regiunea cu cea mai mică poziție din statul cu coordonatele cele mai mici în sens lexicografic

Exemplu:

oaste.in

4 6
0 1 1 0 2 5
9 0 2 0 1 0
0 1 1 0 0 2
0 0 1 1 1 1

oaste.out

2 2 3

Explicație

Harta din fișierul de intrare contine 3 state. Statul cu culoarea rosie in imagine are cei mai multi soldati iar regiunea din pozitia (2,3) are cei mai multi soldati referitor la celelalte regiuni din acest stat.

def in_bounds(x, y, n, m):
    return 0 <= x < n and 0 <= y < m

def dfs(matrix, visited, x, y, n, m):
    stack = [(x, y)]
    visited[x][y] = True
    soldiers_sum = 0
    positions = [(x, y)]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while stack:
        cx, cy = stack.pop()
        soldiers_sum += matrix[cx][cy]
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if in_bounds(nx, ny, n, m) and not visited[nx][ny] and matrix[nx][ny] == matrix[cx][cy]:
                visited[nx][ny] = True
                stack.append((nx, ny))
                positions.append((nx, ny))
    
    return soldiers_sum, positions[0]

def find_strongest_region(matrix):
    n = len(matrix)
    m = len(matrix[0])
    visited = [[False] * m for _ in range(n)]
    
    max_soldiers = 0
    best_position = (-1, -1)
    
    for i in range(n):
        for j in range(m):
            if matrix[i][j] != 0 and not visited[i][j]:
                soldiers, position = dfs(matrix, visited, i, j, n, m)
                if soldiers > max_soldiers:
                    max_soldiers = soldiers
                    best_position = position
    
    return max_soldiers, best_position

# Exemplu de utilizare:
matrix = [
    [1, 1, 0, 3],
    [1, 0, 3, 3],
    [2, 2, 2, 0],
    [2, 0, 0, 0]
]

max_soldiers, position = find_strongest_region(matrix)
print(f"Maxim soldați: {max_soldiers}, Poziție: {position}")