Editing 4081 - alpinistii (section)

==Rezolvare==
<syntaxhighlight lang="python" line="1">
 
def validare(n, m, matrice):
    if n < 1 or n > 200:
        return False
    if m < 1 or m > 200:
        return False
    for i in range(n):
        if len(matrice[i]) != m:
            return False
        for j in range(m):
            if matrice[i][j] != '0' and matrice[i][j] != '1':
                return False
    return True


def rezolvare1(n, m, matrice):
    max_spatii = 0
    for i in range(n):
        for j in range(m):
            if matrice[i][j] == '0':
                count = 0
                queue = [(i, j)]
                while queue:
                    x, y = queue.pop(0)
                    if matrice[x][y] == '0':
                        count += 1
                        matrice[x][y] = '1'
                        if x > 0 and matrice[x-1][y] == '0':
                            queue.append((x-1, y))
                        if x < n-1 and matrice[x+1][y] == '0':
                            queue.append((x+1, y))
                        if y > 0 and matrice[x][y-1] == '0':
                            queue.append((x, y-1))
                        if y < m-1 and matrice[x][y+1] == '0':
                            queue.append((x, y+1))
                max_spatii = max(max_spatii, count)
    return max_spatii


def rezolvare2(n, m, matrice):
    # initializam matricea dp cu 0-uri
    dp = [[0] * m for _ in range(n)]

    # calculam lățimea și înălțimea maximă a unui dreptunghi de spații sigure care include fiecare element
    for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):
            if matrice[i][j] == '0':
                w = dp[i][j+1] + 1 if j < m-1 else 1
                h = dp[i+1][j] + 1 if i < n-1 else 1
                dp[i][j] = min(w, h)

    # calculam aria maximă a unui dreptunghi format doar din spații sigure din matrice
    max_area = 0
    for i in range(n):
        for j in range(m):
            if matrice[i][j] == '0':
                area = dp[i][j] * dp[i][j]
                max_area = max(max_area, area)

    return max_area


if __name__ == '__main__':
    with open('alpinisti.in', 'r') as f:
        cerinta, n, m = map(int, f.readline().strip().split())
        matrice = [list(f.readline().strip().split()) for _ in range(n)]

    if cerinta == 1:
        if not validare(n, m, matrice):
            with open('alpinisti.out', 'w') as f:
                f.write('Date de intrare invalide')
        else:
            max_spatii = rezolvare1(n, m, matrice)
            with open('alpinisti.out', 'w') as f:
                f.write(str(max_spatii))

    elif cerinta == 2:
        max_spatii = rezolvare2(n, m,matrice)
        with open('alpinisti.out', 'w') as f:
            f.write(str(max_spatii))


</syntaxhighlight>