Editing 4013 - CMGB (section)

= 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>