CSES - Seinäpoisto

Annettuna on n \times m -labyrintti, ja tehtäväsi on kulkea ruudusta A ruutuun B.

Tässä tehtävässä labyrintissa on kahdenlaisia seinäruutuja: labyrintin reunalla olevaa seinää merkitään # kuten ennenkin, mutta labyrintin sisällä olevaa seinää merkitään *. Voit rikkoa labyrintin sisällä olevaa seinää, jolloin pystyt kulkemaan vapaammin labyrintissa.

Mikä on pienin mahdollinen määrä seinäruutuja, jotka sinun täytyy rikkoa, jotta pääset maaliin? Voit olettaa, että 1 \le n, m \le 20.

Python

Toteuta tiedostoon breakwall.py funktio count, joka kertoo pienimmän mahdollisen määrän rikottavia seinäruutuja.

def count(r):
    # TODO

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

Java

Toteuta tiedostoon Breakwall.java metodi count, joka kertoo pienimmän mahdollisen määrän rikottavia seinäruutuja.

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

    public static void main(String[] args) {
        Breakwall b = new Breakwall();
        String[] r = {"########",
                      "#*A*...#",
                      "#.*****#",
                      "#.**.**#",
                      "#.*****#",
                      "#..*.B.#",
                      "########"};
        System.out.println(b.count(r)); // 2
    }
}