RaulOtet: Pagină nouă: 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 <...

2024-08-11T06:46:07Z

Pagină nouă: Pe un continent reprezentat printr-o matrice cu <code>n</code> linii și <code>m</code> 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 <code>(i,j)</code> a unei regiuni din matrice este dată de indicele <code>i</code> de linie și indicele <...

New page

Pe un continent reprezentat printr-o matrice cu <code>n</code> linii și <code>m</code> 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 <code>(i,j)</code> a unei regiuni din matrice este dată de indicele <code>i</code> de linie și indicele <code>j</code> coloană al elementului din matrice corespunzător acestei regiuni.

O poziție din matrice ce contine cifra <code>0</code> este o regiune neutră si nu are soldați, iar poziția ce conține o cifră <code>c</code> nenulă este o regiune ce aparține unui stat și are <code>c</code> 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 <code>oaste.in</code> conține pe prima linie numerele naturale <code>n</code> si <code>m</code>, iar pe fiecare dintre următoarele <code>n</code> linii conține câte <code>m</code> cifre, separate prin câte un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>oaste.out</code> 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 =

* <code>n</code> si <code>m</code> vor fi numere naturale cu valori intre <code>1</code> si <code>100</code> inclusiv;
* fiecare element al matricei va avea valori naturale cuprinse intre <code>0</code> si <code>9</code> inclusiv;
* există cel puțin o cifră nenula în matrice
* spunem ca un stat are coordonatele <code>(i,j)</code> în matrice dacă regiunea din poziția <code>(i,j)</code> aparține acestui stat și este regiunea cu cea mai mică poziție în sens lexicografic dintre regiunile statului.
* perechea <code>(i,j)</code> este mai mică în sens lexicografic ca perechea <code>(x,y)</code> dacă <code>i<x</code> sau dacă <code>i=x</code> și <code>j<y</code>
* 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: =
<code>oaste.in</code>
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
<code>oaste.out</code>
2 2 3

=== Explicație ===
Harta din fișierul de intrare contine <code>3</code> state. Statul cu culoarea rosie in imagine are cei mai multi soldati iar regiunea din pozitia <code>(2,3)</code> 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>

2385 - oaste - Revision history