Računalništvo, vaje 2024/04/10

Imamo matriko oz. minsko polje. Premikamo se lahko le dol ali levo. Začnemo v kvadratku s koordinatama \( (0,0) \) in končamo v \( (n -1, m - 1) \), ker je naša matrika velikost \( n \times m \). Predpostavka je, da vhodno in izhodno polje ne vsebujeta mine.

Problema se bomo lotili od zadaj naprej (od izhoda k vhodu). Kvadratek z \( 1 \) ima samo eno možno pot do njega. Kvadratek z \( 2 \) 2 možni poti - če vzamemo za primer \( (n -2, m - 2) \), lahko pridemo do njega bodisi desno-gor ali pa gor-desno. Tako bo dejansko vhodni kvadratek (oz. glede na to, kako bomo mi reševali izhodni) \( (0,0) \) kvadratek vseboval število vseh možnih poti do njega.

Kako določimo te številke? Enostavno, seštejemo števili kvadratkov, ki sta spodaj in desno od tistega, v katerem se trenutno nahajamo.

Nalogo se da rešiti rekurzivno, vendar mi smo se jo z for zankami. Najprej ustvarili matriko ničel prej omenjene velikosti.

polje = [[0 for j in range(m)] for i in range(n)]

S pomočjo for zank se premikamo po i in j od \( n - 1\) do 0 oz analogno za \( m-1 \) do 0.

for i in range(n-1, -1, -1):
    for j in range(m-1, -1, -1):

V navodilih nam olajšajo, kakšni so pogoji, da določimo število možnih poti:

• kvadratek ima vrednost 0, če vsebuje mino
• kvadratek ima vrednost 1, če smo v spodnjem desnem kotu matrike
• kvadratek ima vrednost enako vrednost svojemu sosedu, če je na robu (torej 1)
• kvadratek ima vsoto spodnjega in levega kot vrednost, če je kjerkoli drugje v matriki.

if (i, j) == (n - 1, m - 1): # smo v spodnjem desnem kotu
    polje[i][j] = 1
elif (i, j) in mine: # mina
    polje[i][j] = 0
elif i == n - 1: # desni rob
    polje[i][j] = polje[i][j + 1]
elif j == m - 1: # spodnji rob
    polje[i][j] = polje[i + 1][j]
else:
    polje[i][j] = polje[i][j + 1] + polje[i + 1][j]

Vlečenje vrvi

Imamo \( 2^n \) možnosti.

Za levo skupino:

Začnemo z maso leve skupine \( \{0\} \). Potem dodamo prvo maso \( m_{1} \), kar pomeni, da je so možne vse \( \{0, m_1\} \) (either je \( m_1 \) v levi skupini ali pa je ni). Ko dodamo drugo maso \( m_2 \), dodamo lahko maso v levo v desno in so možne kombinacije \( \{0, m_1, m_2, m_1 + m_2\} \). Stvari zapisujemo v množico in tako ne zapišemo večih enakih elementov.

Potem je potrebno imeti še slovar kot reference point, kakšna je razporeditev mas.