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.

Python

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

Java

Toteuta tiedostoon NewWall.java metodi count, joka antaa pienimmän muutettavien ruutujen määrän.

public class NewWall {
    public int count(String[] r) {
        // TODO
    }

    public static void main(String[] args) {
        NewWall n = new NewWall();
        String[] r = {".....",
                      ".###.",
                      "...#.",
                      "##.#.",
                      "....."};
        System.out.println(n.count(r)); // 2
    }
}