Quinquagintus Tricartius had een groot probleem. Bij de heraanleg van zijn atrium bestelde hij per ongeluk in plaats van vierkante tegels alleen maar driekwartstegels. Deze zien er uit als een L en beslaan ¾ van een \(2 \times 2\) vierkant. Hoe kon hij nu alsnog zijn atrium betegelen zonder nieuwe tegels te moeten kopen? Gelukkig kwam zijn goede vriend, Julius Caesar, op bezoek. Deze aanschouwde de opengebroken vloer, het afvoerputje en de tegels, en zag onmiddelijk een oplossing. “Triviaal,” sprak Julius, “Divide et impera!” En inderdaad, met een verdeel-en-heers algoritme betegelde Quinquagintus zijn vloer perfect.

Het is namelijk mogelijk om ieder vierkant rooster met 1 gat (het afvoerputje), waarbij de dimensie een macht van twee is, op te vullen met driekwartstegels zodat het vakje van het afvoerputje het enige vakje is waar geen tegel op ligt. Zie hieronder een voorbeeld waar het afvoerputje op positie \((2, 2)\) ligt.

Implementeer de interface Betegeling¹ in een klasse genaamd DriekwartsBetegeling. Hiertoe schrijf je volgende methoden:

• Een constructor, public DriekwartsBetegeling(int k), die een nieuwe betegeling initialiseert voor een vierkant met zijde \(2^k\) (niet zijde k!). Deze betegeling sla je op als een rooster van getallen, waarin elke tegel een uniek getal krijgt, zoals in de geannoteerde tekening. Een 0-waarde stelt een (nog) onbetegeld vakje voor. Wanneer alles betegeld is, heeft enkel het afvoer-vakje nog waarde 0.

• Een triviale methode public int zijde() die de lengte van de zijde, \(2^k\), terug geeft.

• Een triviale methode public int tegelnummer(int r, int c) die het nummer van de tegel op rij \(r\)en kolom \(c\) terug geeft.

• Een methode public void plaatsTegel(int r, int c, int d), die een tegel plaatst in het \(2 \times 2\) vierkantje met linkerbovenhoek op rij \(r\) en kolom \(c\). Het ontbrekende vakje ligt ofwel linksboven (\(d = 0\)), rechtsboven (\(d = 1\)), linksonder (\(d = 2\)) of rechtsonder (\(d = 3\)). Zo zullen de oproepen plaatsTegel(1, 1, 3), plaatsTegel(2, 2, 0) en plaatsTegel(1, 5, 2) de drie gekleurde tegels (5, 8 en 6) in de geannoteerde tekening plaatsen. Neem als nummer van de tegel altijd het laagst mogelijke natuurlijk getal dat nog niet voorkomt in het rooster.

• Een methode public void betegel(int r, int c), die de verdeel-en-heers strategie gebruikt om een nieuwe betegeling te maken. In deze nieuwe betegeling ligt het afvoerputje op rij \(r\) en kolom \(c\).

Als cadeautje krijg je hieronder de skeletcode waarin zich reeds de headers van bovenstaande klasse en methoden bevinden, samen met een handige methode om een betegeling af te drukken in prachtige ASCII-art.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.