CSES - Ratsuparit

Annettuna on shakkilauta, jossa on 8 \times 8 ruutua. Joissakin ruuduissa on ratsu.

Tehtäväsi on muodostaa ratsuista mahdollisimman monta paria, jotka uhkaavat toisiaan. Jokainen ratsu voi kuulua enintään yhteen pariin.

Ratsut uhkaavat toisiaan, jos niiden vaaka- ja pystyetäisyyksistä toinen on 1 ja toinen on 2 (shakin sääntöjen mukaisesti).

Laudan kuvauksessa merkki . tarkoittaa tyhjää ruutua ja merkki * tarkoittaa ratsua.

Python

Toteuta tiedostoon knightpairs.py funktio count, joka antaa suurimman parien määrän.

def count(r):
    # TODO

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

Java

Toteuta tiedostoon KnightPairs.java metodi count, joka antaa suurimman parien määrän.

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

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