Annettuna on n \times n -ruudukko, jonka joissain ruuduissa on kolikko.

Yhdellä siirrolla voit kerätä kaikki kolikot haluamaltasi pysty- tai vaakariviltä. Mikä on pienin tarvittava määrä siirtoja kerätä kaikki kolikot?

Ruudukon kuvauksessa merkki . tarkoittaa tyhjää ja merkki X tarkoittaa kolikkoa. Voit olettaa, että 1 \le n \le 20.

Python

Toteuta tiedostoon coingrid.py funktio count, joka ilmoittaa pienimmän määrän siirtoja kerätä kaikki kolikot.

def count(r):
    # TODO

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

Java

Toteuta tiedostoon CoinGrid.java metodi count, joka ilmoittaa pienimmän määrän siirtoja kerätä kaikki kolikot.

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

    public static void main(String[] args) {
        CoinGrid c = new CoinGrid();
        String[] r = {"........",
                      "........",
                      "...X..X.",
                      "........",
                      "....X...",
                      "..X.X..X",
                      "........",
                      "....X..."};
        System.out.println(c.count(r)); // 3
    }
}