Editing 3341 - oaste2 (section)

= Exemplu: =
<code>oaste2.in</code>
 4 6
 0 1 1 0 2 9
 9 0 2 0 1 0
 0 1 1 0 0 2
 0 0 1 1 1 1
<code>oaste2.out</code>
 12 3

=== Explicație ===
Harta din fișierul de intrare contine <code>3</code> state având: <code>12</code> soldați (culoarea rosu – <code>10</code> regiuni), <code>12</code> soldați (culoare galben – <code>3</code> regiuni), <code>9</code> soldați (culoare verde – <code>1</code> regiune)

<syntaxhighlight lang="python" line="1">
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
    region_size = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    state_value = matrix[x][y]
    
    while stack:
        cx, cy = stack.pop()
        soldiers_sum += matrix[cx][cy]
        region_size += 1
        
        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] == state_value:
                visited[nx][ny] = True
                stack.append((nx, ny))
    
    return soldiers_sum, region_size

def find_strongest_state(matrix):
    n = len(matrix)
    m = len(matrix[0])
    visited = [[False] * m for _ in range(n)]
    
    max_soldiers = 0
    min_regions = float('inf')
    
    for i in range(n):
        for j in range(m):
            if matrix[i][j] != 0 and not visited[i][j]:
                soldiers, regions = dfs(matrix, visited, i, j, n, m)
                if soldiers > max_soldiers:
                    max_soldiers = soldiers
                    min_regions = regions
                elif soldiers == max_soldiers:
                    min_regions = min(min_regions, regions)
    
    return max_soldiers, min_regions

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

max_soldiers, min_regions = find_strongest_state(matrix)
print(f"Număr maxim de soldați: {max_soldiers}, Număr minim de regiuni: {min_regions}")
</syntaxhighlight>