Hirviöt

Sinun tulee kulkea $n \times n$ -ruudukossa vasemmasta yläkulmasta oikeaan alakulmaan niin, että liikut joka vuorolla askeleen oikealle tai alaspäin. Mikä on pienin määrä vastaan tulevia hirviöitä, jos valitset reitin optimaalisesti?

Ruudukon kuvauksessa merkki . tarkoittaa lattiaa, merkki # tarkoittaa seinää ja merkki @ tarkoittaa hirviötä. Voit olettaa, että $1 \le n \le 20$. Jos mitään reittiä ei ole olemassa, haluttu vastaus on $-1$.

Python

Toteuta tiedostoon monsters.py funktio count, joka antaa pienimmän hirviöiden määrän.

def count(r):
    # TODO

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

Java

Toteuta tiedostoon Monsters.java metodi count, joka antaa pienimmän hirviöiden määrän.

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

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