1-算法思想之分治法-棋盘覆盖问题

|

算法–分治法之棋盘覆盖

问题描述

在一个2^k×2^k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为——特殊方格，且称该棋盘为——特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

问题分析

2^k×2^k产生的棋盘中的方格数永远会是3的倍数+1，也就是说该类棋盘一定会被正好填满。对于2^k×2^k棋盘，可以被分成4个2^(k-1)×2^(k-1)棋盘，特殊方格如果出现在左上角，则L型骨牌的方向朝向右下角；如果出现在右上角，则L型骨牌的方向朝向左下角；如果出现在左下角，则L型骨牌的方向朝向右上角；如果出现在右下角，则L型骨牌的方向朝向左上角。L型骨牌放置在四个分支棋盘的交界处。

解题思路

分析：当k>0时，将2^k×2^k分割为4个2^(k-1)×2^(k-1)棋盘。特殊方法必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1

算法实现

每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断方法是每次先记录下整个大方块的左上角方格的行列左边，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角、左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要有一个变量s来记录边的方格数，每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。其次还要有一个变nCount来记录L型骨牌的数量。

算法分析

实现定位需要每个棋盘左上角坐标和边的长度，所以递归函数需要5个参数，特殊方格的横坐标Special_X，纵坐标Special_Y，左上角横坐标Top_Left_X，纵坐标Top_Left_Y，棋盘边的长度Size，以此我们可以制定一个递归函数ChessBoard;

代码实现

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
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int nCount = 0;
int Matrix[100][100];

void ChessBoard(int Top_Left_X, int Top_Left_Y, int Special_X, int Special_Y, int Size);

int main()
{
	int Size, Special_X, Special_Y;
	memset(Matrix, 0, sizeof(Matrix));
	scanf_s("%d", &Size);
	scanf_s("%d%d", &Special_X, &Special_Y);
	ChessBoard(0, 0, Special_X, Special_Y, Size);

	for (int i = 0; i < Size; i++)
	{
		for (int j = 0; j < Size; j++)
		{
			printf("%2d ", Matrix[i][j]);
		}
		printf("\n");
	}
}

void ChessBoard(int Top_Left_X, int Top_Left_Y, int Special_X, int Special_Y, int Size)
{
	int s;		//用于记录棋盘的一半长度
	int t;		//用于显示L型骨牌的数量

	if (1 == Size) return;

	s = Size / 2;
	t = ++nCount;

	//【1】对左上子棋盘的处理
	//如果特殊点在左上子棋盘，则不需要另外加点,直接进入下一次递归
	if (Special_X < (Top_Left_X + s) && Special_Y < (Top_Left_Y + s))
	{
		ChessBoard(Top_Left_X, Top_Left_Y, Special_X, Special_Y, s);
	}
	//如果特殊点不在左上子棋盘，则需要在左上子棋盘的右下角加点，再进入下一层递归
	else
	{
		Matrix[Top_Left_X + s - 1][Top_Left_Y + s - 1] = t;
		ChessBoard(Top_Left_X, Top_Left_Y, Top_Left_X + s - 1, Top_Left_Y + s - 1, s);
	}

	//【2】对右上子棋盘的处理
    //如果特殊点在右上子棋盘，则不需要另外加点,直接进入下一次递归
	if (Special_X >= (Top_Left_X + s) && Special_Y < (Top_Left_Y + s))
	{
		ChessBoard(Top_Left_X + s, Top_Left_Y, Special_X, Special_Y, s);
	}
    //如果特殊点不在右上子棋盘，则需要在右上子棋盘的左下角加点，再进入下一层递归
	else
	{
		Matrix[Top_Left_X + s][Top_Left_Y + s - 1] = t;
		ChessBoard(Top_Left_X + s, Top_Left_Y, Top_Left_X + s, Top_Left_Y + s - 1, s);
	}

	//【3】对左下子棋盘的处理
    //如果特殊点在左下子棋盘，则不需要另外加点,直接进入下一次递归
	if (Special_X < (Top_Left_X + s) && Special_Y >= (Top_Left_Y + s))
	{
		ChessBoard(Top_Left_X, Top_Left_Y + s, Special_X, Special_Y, s);
	}
    //如果特殊点不在左下子棋盘，则需要在左下子棋盘的右上角加点，再进入下一层递归
	else
	{
		Matrix[Top_Left_X + s - 1][Top_Left_Y + s] = t;
		ChessBoard(Top_Left_X, Top_Left_Y + s, Top_Left_X + s - 1, Top_Left_Y + s, s);
	}

	//【4】对右下子棋盘的处理
    //如果特殊点在右下子棋盘，则不需要另外加点,直接进入下一次递归
	if (Special_X >= (Top_Left_X + s) && Special_Y >= (Top_Left_Y + s))
	{
		ChessBoard(Top_Left_X + s, Top_Left_Y + s, Special_X, Special_Y, s);
	}
    //如果特殊点不在右下子棋盘，则需要在右下子棋盘的左上角加点，再进入下一层递归
	else
	{
		Matrix[Top_Left_X + s][Top_Left_Y + s] = t;
		ChessBoard(Top_Left_X + s, Top_Left_Y + s, Top_Left_X + s, Top_Left_Y + s, s);
	}
}