【算法设计与分析】棋盘覆盖（递归分治经典问题） |
您所在的位置：网站首页 › 重叠覆盖的定义及解决方案 › 【算法设计与分析】棋盘覆盖（递归分治经典问题） |
【算法设计与分析】棋盘覆盖（递归分治经典问题）
|
本博客主要代码及思路来源：【算法设计与分析（第五版）】【王晓东】 1、题目背景介绍在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 易知，在任何一个2k×2k的棋盘覆盖中，用到的L型骨牌个数恰为(4k-1)/3。
当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。
int tr; /* 棋盘左上角方格所在行号 */ int tc; /* 棋盘左上角方格所在列号 */ int dr; /* 残缺方格所在行号 */ int dc; /* 残缺方格所在列号 * int size; /* 棋盘行数列数 */ int s; /* 子棋盘行列数 */ int t; /* 用于覆盖子棋盘交界处的格板编号 */
下面是全局变量： int tile； // 用于覆盖的 L 型三格板的编号 int board[n][n]；// 棋盘每个方格所覆盖的 L 型三格板的编号 4、实现步骤变量 tile 初值置为0： 1）如果棋盘行列数 size=1，算法结束；否则转步骤 2） 2）按象限分割棋盘为四个子棋盘，子棋盘行列数 s=size/2；用新的 L 型三格板来覆盖，即 tile=tile+1 使 t=tile，子棋盘交界处的方格将用编号为 t 的格板 覆盖。 3）分别按下面的步骤处理四个象限及其交界处的方格。 ① 如果残缺方格位于本象限，则本象限是一个残缺棋 盘，递归调用本算法来覆盖它。否则转步骤 ②。 ② 用编号为 t 的格板覆盖象限交界处方格，把本象限 其余方格作为一个残缺棋盘，递归调用本算法来覆 盖它。 5、代码实现书上代码（第五版在21页） void chessBoard(int tr, int tc, int dr, int dc, int size) { if (size == 1) return; int t = tile++, // 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, tc+s, s); } }完整实现代码： #include /* ChessBoard算法中，用一个二维整型数组Board表示棋盘。 Board[0][0]是棋盘的左上角方格。Board[k][k]：棋盘每个方格所覆盖的L型骨牌的编号 tile是算法中的一个全局整型变量，用来表示L型骨牌的编号，其初始值为0。 int tr; 棋盘左上角方格所在行号 int tc; 棋盘左上角方格所在列号 int dr; 残缺方格所在行号 int dc; 残缺方格所在列号 int size; 棋盘行数列数 int s; 子棋盘行列数 int t; 用于覆盖子棋盘交界处的格板编号 下面是全局变量： int tile； 用于覆盖的 L 型三格板的编号 int Board[n][n]； 棋盘每个方格所覆盖的 L 型三格板的编号 */ #define MaxDim 8 int tile = 0, Board[MaxDim][MaxDim]; void ChessBoard(int tr, int tc, int dr, int dc, int size) { int t, s; if(size == 1) return; tile = tile + 1; 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; /*右下角方格置三格板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; /* 否则,左下角方格置三格板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; /* 否则,右上角方格置三格板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; /* 否则,左上角方格置三格板t */ ChessBoard(tr + s, tc + s, tr + s, tc + s, s); /* 覆盖其余方格 */ } } void PRINT(int ARRAY[][MaxDim]) { int i, j; for(i = 0; i < MaxDim; i++) { for(j = 0; j < MaxDim; j++) printf("%d\t", ARRAY[i][j]); printf("\n"); } } int main() { printf("\n没有填充L型骨牌之前的状态...\n\n"); PRINT(Board); ChessBoard(0, 0, 2, 5, MaxDim); printf("\n填充L型骨牌之后的状态...\n\n"); PRINT(Board); } 六、运行结果
|
【本文地址】
今日新闻 |
推荐新闻 |