算法[递归]-棋盘覆盖问题

Posted on

递归解题的三要素

（1）：最小情况
（2）：原问题与子问题同型
（3）：原问题的解可以用子问题的解来构造

棋盘覆盖问题的描述

在一个2的k次方 X 2的k次方 （此处数学公式的插入待修改）个方格的棋盘中，恰有一个方格与其他方格不同，则称该方格为特殊方格，在棋盘覆盖问题中，要用L型骨牌
覆盖一个带有一个特殊方格的棋盘，特殊方块上不能覆盖骨牌，其他方块上必须有骨牌覆盖，且任意两个骨牌不能重叠覆盖。

解决思路

1、 使用一个二维数组表示棋盘并初始棋盘的每个元素为0
在放置骨牌时同一个骨牌所占的三个方块置为同一个数
因为数组下标是从0开始的原因，所以我们在第一次传入用户所输入的值时刻意减掉一
2、 我们把棋盘分为左上，左下，右上，右下四个区域，分开去处理这四个区域
在处理左上时，根据方块的坐标判断特殊方块是否在此区域内，如果在，那么再递归调用棋盘覆盖函数，如果不在，那么在
此区域的右下角（也就是最靠近棋盘中心的位置）放置骨牌的三分之一。将此方块当作特殊方块，再把这个区域当作棋盘调用棋盘覆盖函数
处理其他三个区域时原理相同。
到棋盘为1x1时便退出。

代码实现

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int ChessBoard(int x, int y, int dx, int dy, int size, int **map);

int title = 1;

int main()
{
    int size;     //定义棋盘的规格
    int dx, dy;     //定义特殊方格的坐标
    int i, j;


    printf("please input the size of the chessboard : \n");
    scanf("%d", &size);

    printf("please input the location of the special chess(eg:(2,3)):\n");
    scanf("%d%d", &dx, &dy);

    int **map = (int **)malloc(sizeof(int *) * size);
    for(i = 0; i <= size; i++){
         *(map + i) = (int *)malloc(sizeof(int) * size);       //动态申请一个二维数组作为棋盘
    }

    for(i = 0; i < size; i++){
        for(j = 0; j < size; j++){
            map[i][j] = 0;                               //初始棋盘的每个值为0。
        }
    }

    ChessBoard( 0, 0, dx - 1, dy - 1, size, map);             //调用函数

    for(i = 0; i < size; i++){                  //打印棋盘
        for(j = 0; j < size; j++){
            printf("%3d",map[i][j]);
        }
        printf("\n");
    }
    return 0;

}

int ChessBoard(int x, int y, int dx, int dy, int size, int **map)
{
     if (size == 1) return -1;
     int t = title++;                //L型骨牌号   便于看清哪几块属于同一个L型骨牌
     int s = size / 2;           //分割棋盘

     //覆盖棋盘左上角
     if(dx < x + s && dy < y + s){              //如果特殊方块在左上角
          ChessBoard(x, y, dx, dy, s, map);          //再次调用此函数
     }else{                                 //如果特殊方块未在此区域
         map[x + s - 1][y + s - 1] = t;         //用t号L型骨牌覆盖此区域右下角
         ChessBoard(x, y, x + s - 1,y + s - 1, s, map); //覆盖其余方格
     }

     //覆盖棋盘右上角 （方法如左上角）
     if(dx < x + s && dy >= y + s){
          ChessBoard(x, y + s, dx, dy, s, map);
     }else{
          map[x + s - 1][y + s] = t;
          ChessBoard(x, y + s, x + s - 1, y + s, s, map);
     }

     //覆盖棋盘左下角
     if(dx >= x + s && dy < y + s){
          ChessBoard(x + s, y, dx, dy, s, map);
     }else{
          map[x + s][y + s - 1] = t;
          ChessBoard(x + s, y,x + s, y + s - 1, s, map);
     }

     //覆盖棋盘右下角
     if(dx >= x + s && dy >= y + s){
          ChessBoard(x + s, y + s, dx, dy, s, map);
     }else{
          map[x + s][y + s] = t;
          ChessBoard(x + s, y + s, x + s, y + s, s, map);
     }
}

感谢阅读，欢迎指正。

-------------本文结束感谢您的阅读-------------