（精）棋盘覆盖问题.ppt

问题描述（一） 在一个 （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，显然，特殊方格在棋盘中出现的位置有 中情形，因而有 中不同的棋盘(如图(a) )。 问题描述（二） 棋盘覆盖问题要求用如图(b)所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 问题分析（一） 问题分析（二） 详细过程图解 如下棋盘中有一个特殊方格 第一次分割 第二次分割 第三次分割 第四次分割为1×1棋盘 第一次分割后子棋盘的覆盖结果 问题求解 下面介绍棋盘覆盖问题中数据结构的设计： （1）棋盘：用二维数组Board[size][size]表示一个棋盘， Board[0][0]是棋盘的左上角方格。其中，size= 。为了在递归处理的过程中使用同一个棋盘，将数组Board设为全局变量； （2）子棋盘：在棋盘数组Board[size][size]中，由子棋盘左上角的下标tr、tc和棋盘边长s表示； （3）特殊方格：用Board[dr][dc]表示，dr和dc是该特殊方格在棋盘数组Board中的下标； （4）L型骨牌：一个 的棋盘中有一个特殊方格，所以用到L型骨牌的个数为( -1)/3将所有L型骨牌从1开始连续编号，用一个全局整型变量tile表示，其初始值为0。 算法的输入参数是： tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:size= ,棋盘规格为 算法—棋盘覆盖 实现这种分治策略的算法ChessBoard如下： void ChessBoard(int tr, int tc, int dr, int dc, int size) // tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标， // size是棋盘的大小，t已初始化为0 { if (size = = 1) return; //棋盘只有一个方格且是特殊方格 t++; // L型骨牌号 s = size/2; // 划分棋盘 // 覆盖左上角子棋盘 if (dr tr + s dc tc + s) // 特殊方格在左上角子棋盘中 ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘 else{ // 用 t 号L型骨牌覆盖右下角，再递归处理子棋盘 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 { // 用 t 号L型骨牌覆盖左下角，再递归处理子棋盘 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 { // 用 t 号L型骨牌覆盖右上角，再递归处理子棋盘 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 { // 用 t 号L型骨牌覆盖左上角，再递归处理子棋盘 board[tr + s][tc + s] = t; ChessBoard(tr+s, tc+s, tr+s,