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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
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[edit | edit source]
n
sim
vor fi numere naturale cu valori intre1
si100
inclusiv;- fiecare element al matricei va avea valori naturale cuprinse intre
0
si9
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
șij<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:[edit | edit source]
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[edit | edit source]
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.
<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 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}") </syntaxhighlight>