Uudet seinät

Annettuna on $n \times n$ -ruudukko, jossa jokainen ruutu on lattiaa tai seinää. Vasemman yläkulman ja oikean alakulman ruudut ovat aina lattiaa eikä niitä voi muuttaa.

Ruudukossa voi liikkua vain oikealle ja alaspäin. Montako ruutua pitää muuttaa vähintään seinäksi, jotta ruudukossa ei ole mitään reittiä vasemmasta yläkulmasta oikeaan alakulmaan?

Ruudukon kuvauksessa merkki . tarkoittaa lattiaa ja merkki # tarkoittaa seinää. Voit olettaa, että $1 \le n \le 20$.

Toteuta tiedostoon newwall.py funktio count, joka antaa pienimmän muutettavien ruutujen määrän.

def count(r):
    # TODO

if __name__ == "__main__":
    r = [".....",
         ".###.",
         "...#.",
         "##.#.",
         "....."]
    print(count(r)) # 2