View source for 2959 - minecraft

== Rezolvare ==
<syntaxhighlight lang="python" line>
def numara_zona_supravietuire(harta, N):
    def dfs(i, j):
        if i < 0 or i >= N or j < 0 or j >= N or harta[i][j] == 'A' or vizitat[i][j]:
            return
        vizitat[i][j] = True
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    vizitat = [[False] * N for _ in range(N)]
    zone_supravietuire = 0

    for i in range(N):
        for j in range(N):
            if harta[i][j] == 'V' and not vizitat[i][j]:
                zone_supravietuire += 1
                dfs(i, j)

    return zone_supravietuire


def zona_maxima_creativ(harta, N):
    def max_histogram_area(histogram):
        stack = []
        max_area = 0
        index = 0

        while index < len(histogram):
            if not stack or histogram[stack[-1]] <= histogram[index]:
                stack.append(index)
                index += 1
            else:
                top_of_stack = stack.pop()
                area = (histogram[top_of_stack] *
                        ((index - stack[-1] - 1) if stack else index))
                max_area = max(max_area, area)

        while stack:
            top_of_stack = stack.pop()
            area = (histogram[top_of_stack] *
                    ((index - stack[-1] - 1) if stack else index))
            max_area = max(max_area, area)

        return max_area

    max_area = 0
    dp = [0] * N

    for i in range(N):
        for j in range(N):
            if harta[i][j] == 'V':
                dp[j] += 1
            else:
                dp[j] = 0
        max_area = max(max_area, max_histogram_area(dp))

    return max_area


def numara_toate_zonele(harta, N):
    zone_supravietuire = 0
    for top in range(N):
        for left in range(N):
            for bottom in range(top, N):
                for right in range(left, N):
                    found_water = False
                    for i in range(top, bottom + 1):
                        for j in range(left, right + 1):
                            if harta[i][j] == 'A':
                                found_water = True
                    if found_water:
                        zone_supravietuire += 1
    return zone_supravietuire


def main():
    K = int(input().strip())
    N = int(input().strip())

    assert 2 <= N <= 1000, "N trebuie sa fie intre 2 si 1000"

    harta = []
    for _ in range(N):
        row = list(input().strip())
        assert len(row) == N, "Fiecare rând trebuie să aibă exact N caractere"
        assert all(c in {'A', 'V'} for c in row), "Harta poate contine doar caracterele 'A' si 'V'"
        harta.append(row)

    if K == 1:
        zone_supravietuire = numara_toate_zonele(harta, N)
        print(f"{zone_supravietuire}")
    elif K == 2:
        zona_creativ = zona_maxima_creativ(harta, N)
        print(f"{zona_creativ}")
    else:
        print("Valoare K invalidă")


if __name__ == "__main__":
    main()

if __name__ == "__main__":
    main()

</syntaxhighlight>