分治算法-棋盘覆盖

 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
67
68
69
70
71
72
73
74
75
76
77

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-04-24 18:05:38
 * 最后修改: 2026-05-01 09:38:30
 * 文件描述: 分治  棋盘覆盖
****************************************************************/

#include <iostream>
#include <iomanip>
using namespace std;
int board[65][65], tile; /* tile 用于给每个 L 型骨牌编号 */

// 递归覆盖 chessboard：在 row/column 为左上角、size 为边长的棋盘中，
// 让 (x, y) 这个特殊方格不被覆盖，其余区域全部用 L 型骨牌铺满。
void chessboard( int row, int column, int x, int y, int size ){
	int t, s;

	if ( size == 1 ) return;// 递归终止：1×1 棋盘无需再铺
	t = ++tile;// 当前这层递归分配一个新的骨牌编号
	s = size / 2;

	
	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 );
    }

	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 );
	}

	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 );
	}

	
	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 );
}