CSES - Seinät ja lattiat

Ruudukossa on n \times n ruutua, joista jokainen on aluksi seinää. Rivit ja sarakkeet on numeroitu 1 \dots n. Ruudukosta aletaan poistaa seinää muuttamalla seinäruutuja lattiaruuduiksi.

Tehtäväsi on pitää kirjaa huoneiden määrästä tässä prosessissa. Huoneissa lattiaruutuja voi kulkea vaaka- ja pystysuuntaisesti, kuten aiemmissa kurssin tehtävissä.

Voit olettaa, että n on enintään 100 ja luokan metodeita kutsutaan enintään 10000 kertaa. Lisäksi reunaruutuja ei koskaan muuteta lattiaksi.

Python

Toteuta tiedostoon wallgrid.py luokka WallGrid, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan ruudukon koko
  • remove muuttaa ruudun (x,y) lattiaksi, mikäli se ei jo ole lattiaa
  • count ilmoittaa, montako huonetta ruudukossa on
class WallGrid:
    def __init__(self,n):
        # TODO

    def remove(self,x,y):
        # TODO

    def count(self):
        # TODO

if __name__ == "__main__":
    w = WallGrid(5)
    print(w.count()) # 0
    w.remove(2,2)
    w.remove(4,2)
    print(w.count()) # 2
    w.remove(3,2)
    print(w.count()) # 1
    w.remove(2,4)
    w.remove(2,4)
    w.remove(4,4)
    print(w.count()) # 3
    w.remove(3,3)
    print(w.count()) # 3
    w.remove(3,4)
    print(w.count()) # 1

Java

Toteuta tiedostoon WallGrid.java luokka WallGrid, jossa on seuraavat metodit:

  • konstruktori, jolle annetaan ruudukon koko
  • remove muuttaa ruudun (x,y) lattiaksi, mikäli se ei jo ole lattiaa
  • count ilmoittaa, montako huonetta ruudukossa on
public class WallGrid {
    public WallGrid(int n) {
        // TODO
    }

    public void remove(int x, int y) {
        // TODO
    }

    public int count() {
        // TODO
    }

    public static void main(String[] args) {
        WallGrid w = new WallGrid(5);
        System.out.println(w.count()); // 0
        w.remove(2,2);
        w.remove(4,2);
        System.out.println(w.count()); // 2
        w.remove(3,2);
        System.out.println(w.count()); // 1
        w.remove(2,4);
        w.remove(2,4);
        w.remove(4,4);
        System.out.println(w.count()); // 3
        w.remove(3,3);
        System.out.println(w.count()); // 3
        w.remove(3,4);
        System.out.println(w.count()); // 1
    }
}