棋盘覆盖算法分布动态显示

1. 求NOIP2007普及组初赛试题（棋盘覆盖问题）的程序解析，比如程序的思路以及每步的作用

声明：本文使用的代码和例子的来源：《计算机算法设计与分析》（王晓东编着，电子工业出版社）。我对代码做了少许修改，使可以在tc的图形模式下看到题目的结果。

题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。现在要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），切任何两个L型方块不能重叠覆盖。L型方块的形态如下：

■■*■■***■*■
■******■*■■*■■

题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，知道子棋盘的大小为1为止。
用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法。

2. 棋盘覆盖问题的算法分析

设T(k)是算法ChessBoard覆盖一个2^k×2^k棋盘所需时间，从算法的划分
策略可知，T(k)满足如下递推式：
T(k) = 1 当k=0时
T(k) = 4T(k-1) 当k>0时
解此递推式可得T(k)=O(4^k)。

3. 棋盘覆盖算法

import java.util.*;

public class TestChessBoard {
public static void main(String[] args) {
int tr=0,tc=0,dr=1,dc=2,size=8;
ChessBoard.chessBoard(tr,tc,dr,dc,size);
ChessBoard.display();
}
}

class ChessBoard {
public static int tile = 0;
public static int[][] board= new int[10][10];
public static void chessBoard (int tr,int tc,int dr,int dc,int size) {

if(size == 1) return;
int t = tile++ , s = size/2;
if(dr<tr+s && dc<tc+s){
chessBoard(tr,tc,dr,dc,s);
}else {
board[tr+s-1][tc+s-1] = t;
chessBoard(tr,tc,tr+s-1,tc+s-1,s);
}

if(dr<tr+s && dc>=tc+s){
chessBoard(tr,tc+s,dr,dc,s);
}else {
board[tr+s-1][tc+s] = t;
chessBoard(tr,tc+s,tr+s-1,tc+s,s);
}

if(dr>=tr+s && dc<tc+s) {
chessBoard(tr+s,tc,dr,dc,s);
}else {
board[tr+s][tc+s-1] = t;
chessBoard(tr+s,tc,tr+s,tc+s-1,s);
}

if(dr>=tr+s && dc>=tc+s) {
chessBoard(tr+s,tc+s,dr,dc,s);
}else {
board[tr+s][tc+s] = t;
chessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
}

public static void display() {
for(int i=0;i<8;i++){
for(int j=0;j<8;j++) {
System.out.print(" "+board[i][j]);
}
System.out.println();
}
}
}

4. NOI考试的内容是什么

1 时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析方法，主定理）
2 排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）
3 数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余方程，中国剩余定理）
4 指针（链表，搜索判重，邻接表，开散列，二叉树的表示，多叉树的表示）
5 按位运算（and，or，xor，shl，shr，一些应用）
6 图论（图论模型的建立，平面图，欧拉公式与五色定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最小生成树的三种算法，最短路的三种算 法，标号法，差分约束系统，验证二分图，Konig定理，匈牙利算法，KM算法，稳定婚姻系统，最大流算法，最小割最大流定理，最小费用最大流算法）
7 计算几何（平面解几及其应用，向量，点积及其应用，叉积及其应用，半平面相交，求点集的凸包，最近点对问题，凸多边形的交，离散化与扫描）
8 数据结构（广度优先搜索，验证括号匹配，表达式计算，递归的编译，Hash表，分段Hash，并查集，Tarjan算法，二叉堆，左偏树，斜堆，二项堆，二叉查找树，AVL，Treap，Splay，静态二叉查找树，2-d树，线段树，二维线段树，矩形树，Trie树，块状链表）
9 组合数学（排列与组合，鸽笼原理，容斥原理，递推，Fibonacci数列，Catalan数列，Stirling数，差分序列，生成函数，置换，Polya原理）
10 概率论（简单概率，条件概率，Bayes定理，期望值）
11 矩阵（矩阵的概念和运算，二分求解线性递推方程，多米诺骨牌棋盘覆盖方案数，高斯消元）
12 字符串处理（KMP，后缀树，有限状态自动机，Huffman编码，简单密码学）
13 动态规划（单调队列，凸完全单调性，树型动规，多叉转二叉，状态压缩类动规，四边形不等式）
14 博奕论（Nim取子游戏，博弈树，Shannon开关游戏）
15 搜索（A*，ID，IDA*，随机调整，遗传算法）
16 微积分初步（极限思想，导数，积分，定积分，立体解析几何）

5. 棋盘覆盖问题的算法实现

下面讨论棋盘覆盖问题中数据结构的设计。
（1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量；
（2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示；
（3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标;
（4） L型骨牌：一个2^k×2^k的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4^k-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。
设全局变量t已初始化为0，分治法求解棋盘覆盖问题的算法用C++语言描述如下：
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
int s, t1; //t1表示本次覆盖所用L型骨牌的编号
if (size == 1) return; //棋盘只有一个方格且是特殊方格
t1 = ++t; // L型骨牌编号
s = size/2; // 划分棋盘
if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盘中
ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘
else{ //用 t1号L型骨牌覆盖右下角，再递归处理子棋盘
board[tr + s - 1][tc + s - 1] = t1;
ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
}
if (dr < tr + s && dc >= tc + s) //特殊方格在右上角子棋盘中
ChessBoard(tr, tc+s, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖左下角，再递归处理子棋盘
board[tr + s - 1][tc + s] = t1;
ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
}
if (dr >= tr + s && dc < tc + s) //特殊方格在左下角子棋盘中
ChessBoard(tr+s, tc, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖右上角，再递归处理子棋盘
board[tr + s][tc + s - 1] = t1;
ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
}
if (dr >= tr + s && dc >= tc + s) //特殊方格在右下角子棋盘中
ChessBoard(tr+s, tc+s, dr, dc, s); //递归处理子棋盘
else { //用 t1号L型骨牌覆盖左上角，再递归处理子棋盘
board[tr + s][tc + s] = t1;
ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
}
}