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