分治算法-棋盘覆盖

棋盘覆盖问题)在一个 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

Scroll to Top