棋盘覆盖算法（JAVA实现）
标签： 棋盘覆盖算法（JAVA实现） 博客 51CTO博客
2023-07-14 18:24:15 86浏览
棋盘覆盖算法（经典算法问题）
经典算法问题：在一个2k×2k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4k种，因而有4k种不同的棋盘，下图（1）所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用图（2）所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
图（1）
图（2）
如何应用分治法求解棋盘覆盖问题呢？
分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k>0时，可将2k×2k的棋盘划分为4个2（k-1）×2（k-1）的子棋盘，如图4.11(a)所示。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图4.11(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。
算法设计
package com.bean.algorithm.basic;
public class ChessProblem {
int size;// 容量
int[][] board;// 棋盘
int specialROW;// 特殊点横坐标
int specialCOL;// 特殊点纵坐标
int number = 0;// L形编号
public ChessProblem(int specialRow, int specialCol, int size) {
this.size = size;
this.specialCOL = specialCOL;
this.specialROW = specialROW;
board = new int[size][size];
}
// specialROW 特殊点的行下标
// specialCOL 特殊点的列下标
// leftRow 矩阵的左边起点行下标
// leftCol 矩阵左边起点的列下标
// size 矩阵的宽或者高
public void setBoard(int specialROW, int specialCOL, int leftROW, int leftCOL, int size) {
if (1 == size) {
return;
}
int subSize = size / 2;
number++;
int n = number;// 注意这里一定要吧number存在当前的递归层次里，否则进入下一层递归全局变量会发生改变
// 假设特殊点在左上角区域
if (specialROW < leftROW + subSize && specialCOL < leftCOL + subSize) {
setBoard(specialROW, specialCOL, leftROW, leftCOL, subSize);
} else {
// 不在左上角，设左上角矩阵的右下角就是特殊点（和别的一起放置L形）
board[leftROW + subSize - 1][leftCOL + subSize - 1] = n;
setBoard(leftROW + subSize - 1, leftCOL + subSize - 1, leftROW, leftCOL, subSize);
}
// 假设特殊点在右上方
if (specialROW < leftROW + subSize && specialCOL >= leftCOL + subSize) {
setBoard(specialROW, specialCOL, leftROW, leftCOL + subSize, subSize);
} else {
// 不在右上方，设右上方矩阵的左下角就是特殊点（和别的一起放置L形）
board[leftROW + subSize - 1][leftCOL + subSize] = n;
setBoard(leftROW + subSize - 1, leftCOL + subSize, leftROW, leftCOL + subSize, subSize);
}
// 特殊点在左下方
if (specialROW >= leftROW + subSize && specialCOL < leftCOL + subSize) {
setBoard(specialROW, specialCOL, leftROW + subSize, leftCOL, subSize);
} else {
// 不在左下方，设左下方矩阵的右上角就是特殊点（和别的一起放置L形）
board[leftROW + subSize][leftCOL + subSize - 1] = n;
setBoard(leftROW + subSize, leftCOL + subSize - 1, leftROW + subSize, leftCOL, subSize);
}
// 特殊点在右下角
if (specialROW >= leftROW + subSize && specialCOL >= leftCOL + subSize) {
setBoard(specialROW, specialCOL, leftROW + subSize, leftCOL + subSize, subSize);
} else {
// 不在右下角，设右下角矩阵的左上就是特殊点（和别的一起放置L形）
board[leftROW + subSize][leftCOL + subSize] = n;
setBoard(leftROW + subSize, leftCOL + subSize, leftROW + subSize, leftCOL + subSize, subSize);
}
}
public void printBoard(int specialRow, int specialCol, int size) {
setBoard(specialRow, specialCol, 0, 0, size);
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int N = 4;
int specialRow = 0;
int specialCol = 1;
ChessProblem chessProblem = new ChessProblem(specialRow, specialCol, N);
chessProblem.printBoard(specialRow, specialCol, N);
}
}程序运行结果
2 0 3 3
2 2 1 3
4 1 1 5
4 4 5 5
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
