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. Ruudukon kuvauksessa merkki . tarkoittaa lattiaa ja merkki # tarkoittaa seinää.

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?

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

def min_changes(grid):
    # TODO

if __name__ == "__main__":
    grid = ["...#.",
            "...#.",
            "####.",
            ".....",
            "....."]

    print(min_changes(grid)) # 0

    grid = [".#...",
            "...#.",
            "...#.",
            ".###.",
            ".###."]

    print(min_changes(grid)) # 0

    grid = [".#...",
            "...#.",
            "...#.",
            ".###.",
            "....."]

    print(min_changes(grid)) # 1

    grid = [".....",
            ".###.",
            "...#.",
            "##.#.",
            "....."]

    print(min_changes(grid)) # 2