Rus Marius: Pagină nouă: == Enunț == Cunoscutul programator Văndămel are la dispoziție o matrice binară cu `n` linii (numerotate de la `1` la `n`) și `m` coloane (numerotate de la `1` la `m`). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea `1` și le transformă în `0`. De exemplu, în matricea:...

2024-01-06T20:22:14Z

Pagină nouă: == Enunț == Cunoscutul programator Văndămel are la dispoziție o matrice binară cu <code>n</code> linii (numerotate de la <code>1</code> la <code>n</code>) și <code>m</code> coloane (numerotate de la <code>1</code> la <code>m</code>). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea <code>1</code> și le transformă în <code>0</code>. De exemplu, în matricea:...

New page

== Enunț ==
Cunoscutul programator Văndămel are la dispoziție o matrice binară cu <code>n</code> linii (numerotate de la <code>1</code> la <code>n</code>) și <code>m</code> coloane (numerotate de la <code>1</code> la <code>m</code>). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea <code>1</code> și le transformă în <code>0</code>. De exemplu, în matricea:

<code>0 1 1 0</code>

<code>1 1 0 0</code>

<code>1 0 0 0</code>

<code>0 1 1 0</code>

el poate alege valorile de <code>1</code> de la pozițiile vecine <code>(1,2)</code> și <code>(2,2)</code>, le transformă în <code>0</code> și obține matricea:

<code>0 0 1 0</code>

<code>1 0 0 0</code>

<code>1 0 0 0</code>

<code>0 1 1 0</code>

= Cerința =
Văndămel știe să rezolve orice problemă, dar vrea să vadă dacă știți și voi să aflați numărul maxim posibil de operații care se pot efectua pe matricea dată.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>m</code> și de pe următoarele <code>n</code> linii câte <code>m</code> numere binare reprezentând valorile din matrice.

= Date de ieșire =
Programul va afișa pe ecran un singur număr natural reprezentând numărul maxim posibil de operații care se pot aplica asupra matricei.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n, m ≤ 100</code>

= Exemplul 1: =
Intrare
4 4
0 1 1 0
1 1 0 0
1 0 0 0
0 1 1 0
Ieșire
3

=== Explicație ===
Se efectuează operațiile la <code>(2,1)</code> și <code>(3,1)</code>, la <code>(1,2)</code> și <code>(2,2)</code> și la <code>(4,2)</code> și <code>(4,3)</code>. După efectuarea celor <code>3</code> operații matricea arată astfel:

== Exemplul 2: ==
Intrare
101 101
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
Nmax = 100001

oo = 1 << 28
VI = list[int]

n, m, p, v, im = 0, 0, 0, 0, 0
M = [[0]*202 for _ in range(202)]
A = [[0]*202 for _ in range(202)]
U = [0]*10001
D = [0]*10001
Vis = [False] * Nmax
V = [[] for _ in range(Nmax)]

def check_constraints(n, m):
if not (1 <= n <= 100) or not (1 <= m <= 100):
print("Datele nu corespund restrictiilor impuse")
return False
return True

def cupleaza(v):
if Vis[v]:
return 0

Vis[v] = 1

for x in V[v]:
if not D[x]:
U[v] = x
D[x] = v
return True

for x in V[v]:
if cupleaza(D[x]):
U[v] = x
D[x] = v
return True

return False

def main():
global n, m, p, v, im, M, A, U, D, Vis, V

n, m = map(int, input().split())

if not check_constraints(n, m):
return

for i in range(1, n + 1):
row = list(map(int, input().split()))
for j in range(1, m + 1):
M[i][j] = row[j - 1]

if M[i][j] == 1:
if (i + j) % 2 == 0:
p += 1
A[i][j] = p
else:
im += 1
A[i][j] = im

for i in range(1, n + 1):
for j in range(1, m + 1):
if M[i][j] == 1 and (i + j) % 2 == 0:
if M[i + 1][j]: V[A[i][j]].append(A[i + 1][j])
if M[i][j + 1]: V[A[i][j]].append(A[i][j + 1])
if M[i - 1][j]: V[A[i][j]].append(A[i - 1][j])
if M[i][j - 1]: V[A[i][j]].append(A[i][j - 1])

done = 0
ans = 0

while not done:
done = 1

for i in range(p + 1):
Vis[i] = 0

for i in range(1, p + 1):
if U[i] == 0 and cupleaza(i):
ans += 1
done = 0

print(ans)

if __name__ == "__main__":
main()

</syntaxhighlight>

4013 - CMGB - Revision history