In diesem Artikel wird das von Java implementierte Schachbrettabdeckungsproblem beschrieben, das auf der Partitionierung und dem Erobereralgorithmus basiert. Teilen Sie es für Ihre Referenz wie folgt weiter:
In einem Schachbrett, das aus 2^k * 2^K -Quadraten besteht, gibt es ein Quadrat, das sich von den anderen unterscheidet. Wenn die folgenden vier L-förmigen Dominosteine verwendet werden, um andere Quadrate mit Ausnahme dieses speziellen Quadrats abzudecken, wie man sie bedeckt. Die vier L-förmigen Dominosteine sind unten gezeigt:
Die speziellen Quadrate im Schachbrett sind in der Abbildung dargestellt:
Das Grundprinzip der Implementierung besteht darin, das 2^k * 2^k -Schachbrett in vier 2^(k - 1) * 2^(k - 1) Teilschildbrett zu unterteilen. Das spezielle Quadrat muss sich in einem der Sub-Chessboards befinden. Wenn sich das spezielle Quadrat in einem bestimmten Unterschildbrett befindet, verarbeiten Sie das Unterschildbrett weiterhin rekursiv, bis in diesem Subschildbrett nur ein Quadrat vorhanden ist. Wenn sich das spezielle Quadrat nicht in einem bestimmten Unterschildbrett befindet, stellen Sie die entsprechende Position in der Subschildbrett als Domino-Nummer ein, konvertieren Sie die Platine ohne spezielle Quadrate in ein Subschildbrett mit speziellen Quadraten und verarbeiten Sie dann rekursiv das Unterschild. Das obige Prinzip ist in der Abbildung dargestellt:
Der spezifische Code lautet wie folgt:
Package Demo; öffentliche Klasse -Schach { /*tr tritt die Zeilennummer der oberen linken Ecke des Schachbretts an, die Spaltennummer der oberen linken Ecke des Schachbretts, die Zeilennummer des speziellen Schachbretts, DC zeigt die Spaltennummer des speziellen Schachbretts* / public static void Chessboard (int tc, int dr, int dc, int dc, int dc, int dc, int dc, int dc, int. } int t = title ++; int s = Größe/2; // Abdecken Sie die obere linke Ecke des Schachbretts if (dr <tr + s && dc <tc + s) {// Spezialquadrat in diesem Schachbrett (TR, TC, DR, DC, S); } else {// Es gibt kein spezielles Quadrat in dieser Tafel, bedecken Sie die untere rechte Ecke mit T -Number -L -förmigen Dominosteinen [tr + s -1] [tr + s -1] = t; // den Rest des quadratischen Schachbretts abdecken (TR, TC, TC + S - 1, TC + S - 1, S); } // Abdecken Sie die obere rechte Ecke if (dr <tr + s && dc> = tc + s) {// Speziales quadratisches Schachbrett (tr, tc + s, dr, dc, s); } else {// Dieses Board hat mittags ein spezielles Quadrat. Decken Sie die untere linke Ecke mit T-Number-L-förmigen Dominosteinen [tr + s-1] [tc + s] = t; // Abdecken Sie den Rest des quadratischen Schachbretts (TR, TC + S, TR + S - 1, TC + S, S); } // Abdecken Sie die untere linke Eckeschachbrett if (dr> = tr + s && dc <tc + s) {// Speziales Quadrat in dieser Board -Schachbrett (Tr + S, TC, DR, DC, S); } else {// Es gibt kein spezielles Quadrat in dieser Platine, bedecken Sie die obere rechte Ecke [tr + s] [tr + s -1] = t; // das andere Quadrateschachbrett abdecken (TR, TC, TC + S, TC + S - 1, S); } // Abdecken Sie das Schachbrett der unteren rechten Ecke (tr> = tr + s && dc> = tc + s) {// Speziales Quadrat in diesem Board -Schach (Tr + S, Tc + S, Dr, DC, S); } else {// Es gibt kein spezielles Quadrat in dieser Platine. Verwenden Sie das T-Number-L-förmige Domino, um die obere linke Eckplatte zu decken [tr + s] [tc + s] = t; // Abdecken Sie das verbleibende Quadrateschachbrett (TR + S, TC + S, TC + S, TC + S, S); }} @Suppresswarnings ("static-access") public static void main (String args []) {System.out.println ("Wulin.com Testergebnisse:"); Board [2] [2] = 0; Schach CH = neuer Schach (); Ch.Chessboard (0, 0, 2, 2, Größe); für (int i = 0; i <size; ++ i) {für (int j = 0; j <size; j ++) {system.out.print (board [i] [j]+""); } System.out.println (); }} statische endgültige int size = 4; statischer Int -Titel = 1; static int board [] [] = new int [Größe] [Größe];}Auslaufergebnisse:
Für weitere Informationen zu Java -Algorithmen können Leser, die an dieser Website interessiert sind, die Themen "Java -Datenstruktur und Algorithmus -Tutorial", "Zusammenfassung der Java -Operation DOM -Knoten -Tipps", "Zusammenfassung der Java -Datei- und Verzeichnisoperationstipps" und "Zusammenfassung der Java -Cache -Operation Tipps" anzeigen
Ich hoffe, dieser Artikel wird für Java -Programme aller hilfreich sein.