Este artigo descreve o problema de cobertura do tabuleiro de xadrez implementado pelo Java com base no algoritmo de particionamento e conquista. Compartilhe -o para sua referência, como segue:
Em um quadro de xadrez composto por quadrados 2^K * 2^K, há um quadrado diferente dos outros. Se os quatro dominó de forma L a seguir forem usados para cobrir outros quadrados, exceto este quadrado especial, como cobri-los. Os quatro dominó em forma de L são mostrados abaixo:
Os quadrados especiais no tabuleiro de xadrez são mostrados na figura:
O princípio básico da implementação é dividir o tabuleiro de xadrez 2^k * 2^K em quatro 2^(k - 1) * 2^(K - 1) Sub -Chessboard. O quadrado especial deve estar em uma das pranchas sub-quietas. Se o quadrado especial estiver em um certo sub-quadro, continue processando recursivamente a prancha de subsídio até que haja apenas um quadrado neste subsídio. Se o quadrado especial não estiver em um determinado quadro de sub-quilômetro, defina a posição correspondente na placa de subsídio como o número do dominó, converta a placa sem quadrados especiais em uma prancha de subsídio com quadrados especiais e processe recursivamente o sub-quadro. O princípio acima é mostrado na figura:
O código específico é o seguinte:
Pacote Demo; Public Class Chess { /*TR indica o número da linha do canto superior esquerdo do tabuleiro de xadrez, o número da coluna do canto superior esquerdo do tabuleiro de xadrez, o número da linha do tabuleiro de xadrez especial, DC indica o número da coluna If If (If Return «se Return); } int t = title ++; int s = size/2; // cubra o canto superior esquerdo do tabuleiro de xadrez if (dr <tr + s && dc <tc + s) {// quadrado especial neste tabuleiro de xadrez (tr, tc, dr, dc, s); } else {// Não existe um quadrado especial nesta placa, cubra o canto inferior direito com dominó de Number L de T [tr + s -1] [tr + s -1] = t; // Cubra o restante do quadro de xadrez quadrado (TR, TC, TC + S - 1, TC + S - 1, S); } // Cubra o canto superior direito se (dr <tr + s && dc> = tc + s) {// square square squessboard (tr, tc + s, dr, dc, s); } else {// Esta placa possui um quadrado especial ao meio-dia, cubra o canto inferior esquerdo com dominoes em forma de L do número T [tr + s-1] [tc + s] = t; // Cubra o restante do quadro de xadrez quadrado (TR, TC + S, TR + S - 1, TC + S, S); } // Cubra o quadro de xadrez do canto inferior esquerdo if (dr> = tr + s && dc <tc + s) {// quadrado especial neste quadro de xadrez (tr + s, tc, dr, dc, s); } else {// não existe um quadrado especial nesta placa, cubra a placa do canto superior direito [tr + s] [tr + s -1] = t; // Cubra os outros quadros de xadrez quadrados (TR, TC, TC + S, TC + S - 1, S); } // Cubra o quadro de xadrez do canto direito inferior (tr> = tr + s && dc> = tc + s) {// quadrado especial neste quadro de xadrez (tr + s, tc + s, dr, dc, s); } else {// Não existe um quadrado especial nesta placa, use o dominó em forma de L-Number L para cobrir a placa do canto esquerdo superior [tr + s] [tc + s] = t; // Cubra os quadrados restantes de xadrez (tr + s, tc + s, tc + s, tc + s, s); }} @Suppresswarnings ("estático-access") public static void main (string args []) {system.out.println ("wulin.com Resultados dos testes:"); Placa [2] [2] = 0; Xadrez ch = novo xadrez (); Ch.Chessboard (0, 0, 2, 2, tamanho); for (int i = 0; i <tamanho; ++ i) {for (int j = 0; j <size; j ++) {System.out.print (placa [i] [j]+""); } System.out.println (); }} final estático int size = 4; static int title = 1; estático int board [] [] = new int [size] [size];}Resultados em execução:
Para obter mais informações sobre os algoritmos Java, os leitores interessados neste site podem visualizar os tópicos: "Estrutura de dados Java e tutorial de algoritmo", "Resumo das dicas de nó da operação Java Dom", "Resumo de dicas de operação de Java e Operação de Java" e "Resumo de Java cache" Tips "TIPS"
Espero que este artigo seja útil para a programação Java de todos.