分治算法-棋盘覆盖
棋盘覆盖问题）在一个 2k×2k 个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为 −1 的方格），称之为特殊方格。现 L 型（占 3 个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是 (4k−1)/3。在下表给出的一个覆盖方案中，k=2，相同的 3 各数字构成一个纸片。下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。
2 2 3 3
2 -1 1 3
4 1 1 5
4 4 5 5
代码实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <iostream> #include <iomanip> using namespace std; int board[65][65], tile; /* tile为纸片编号 */ void chessboard( int row, int column, int x, int y, int size ){ /* x,y依次为特殊方格的行、列号 */ /* row, column为整个大方格的起始位置*/ int t,s; if ( size == 1 )return ; t = ++tile; s = size / 2; // upper left square if ( x<row+s&& y<column+s ) chessboard( row, column, x, y, s ); else{ board[row + s -1][column + s -1] = t; chessboard(row,column,row+s-1,column+s-1,s); } // upper right square if ( x < row + s && y >= column + s ) chessboard( row, column + s, x, y, s ); else{ board[row + s -1][column + s] = t; chessboard(row,column+s,row+s-1,column+s,s); } //down left square if ( x >= row + s && y < column + s ) chessboard( row + s, column, x, y, s ); else{ board[row + s][column + s -1] = t; chessboard(row+s,column,row+s,column+s-1,s); } //down right square if ( x >= row + s && y >= column + s ) chessboard( row + s, column + s, x, y, s ); else{ board[row + s][column + s] = t; chessboard(row+s,column+s,row+s,column+s,s); } } void princolumnhessboard( int b[][65], int n ) { int i, j; for ( i =1; i <= n; i++ ) { for ( j =1; j <= n; j++ ) cout << setw( 3 ) << b[i][j]; // setw(3) output three characters field width. cout << endl; } } int main(){ int size, x, y; cout << "input size(4/8/16/64):" << endl; cin >> size; cout << "input the position of special block(x,y):" << endl; cin >> x >> y; board[x][y] = -1; chessboard( 1, 1, x, y, size ); princolumnhessboard( board, size ); } |
洛谷：P1911