1.3 Najwięcej czarnych pól

Matura maj 2024 - Matura z informatyki: arkusze krok po kroku (Python)

Zadanie 1.3 (1 pkt): największa liczba czarnych pól na planszy \( n \times n \), dla której wynik to PRAWDA. Droga z lewego górnego do prawego dolnego rogu, w prawo i w dół, przechodzi zawsze przez \( 2n - 1 \) pól, które muszą być białe. Reszta może być czarna. Program sprawdza to dla małych plansz wszystkimi możliwymi kolorowaniami (dla \( n = 3 \) to \( 2^9 = 512 \) plansz): kolejne bity liczby `code` mówią, które pola są białe.

def result(A):
    # algorytm z arkusza; w Pythonie wiersze i kolumny liczy się od 0, więc A[0][0] to lewy
    # górny róg, a A[n - 1][m - 1] prawy dolny
    n, m = len(A), len(A[0])
    P = [[False] * m for i in range(n)]
    P[0][0] = True
    for i in range(n):
        for j in range(m):
            if A[i][j] == 0:
                P[i][j] = False
            elif i == 0 and j != 0:
                P[i][j] = P[i][j - 1]
            elif i != 0 and j == 0:
                P[i][j] = P[i - 1][j]
            elif i != 0 and j != 0:
                P[i][j] = P[i][j - 1] or P[i - 1][j]
    return P[n - 1][m - 1]


for n in [2, 3]:
    best = 0
    for code in range(2 ** (n * n)):
        A = [[(code >> (i * n + j)) & 1 for j in range(n)] for i in range(n)]
        if A[0][0] == 1 and A[n - 1][n - 1] == 1 and result(A):
            best = max(best, n * n - sum(sum(row) for row in A))
    print(n, best)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.