紫書_第八章_高效算法設計_8.3.1——棋盤覆寫問題

分治——棋盤覆寫問題

在一個2k x 2k ( 即：2^k x 2^k )個方格組成的棋盤中，恰有一個方格（黑）與其他方格（白）不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆寫問題中，要用圖示的4種不同形态的L型骨牌覆寫給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆寫。

    這裡我們用分治法解決該問題。分治法是把一個規模很大的問題分解為多個規模較小、類似的子問題，然後遞歸地解決所有子問題，最後再由子問題的解決得到原問題的解決。

思路：

先把原方塊分成四塊，而黑色的那一塊一定在其中一塊中，為了遞歸求解，我們在其他三塊上分别在原方塊中心處填上一個方塊，而這三個方塊正好組成了一個L型骨牌。也就是填上了一個，用一個數進行标記，以後處理方式與此相同，我們進行遞歸求解。

下面上代碼：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
int tile=1;//标志序号，根據其可以組成方塊
int board[100][100];//用于記錄
void chessBoard(int tr/*開始x坐标*/, int tc/*開始y坐标*/, int dr/*黑色x坐标*/, int dc/*黑車y坐标*/, int size)
{
    if(size==1)//當其大小為1是傳回
        return;
    int t=tile++;
    int s=size/2;//分為4個
      
    if(dr<tr+s && dc<tc+s)//判斷黑色格是否在左上角的區域
        chessBoard(tr, tc, dr, dc, s);//在則直接繼續遞歸
    else//否則，另右下角格變為黑，并給其賦t值
    {
        board[tr+s-1][tc+s-1]=t;
        chessBoard(tr, tc, tr+s-1, tc+s-1, s);
    }

    if(dr<tr+s && dc>=tc+s)//右上角區域
        chessBoard(tr, tc+s, dr, dc, s);
    else
    {
        board[tr+s-1][tc+s]=t;//區域左下賦t值
        chessBoard(tr, tc+s, tr+s-1, tc+s, s);
    }

    if(dr>=tr+s && dc<tc+s)//左下角區域
        chessBoard(tr+s, tc, dr, dc, s);
    else
    {
        board[tr+s][tc+s-1]=t;//區域右下賦t值
        chessBoard(tr+s, tc, tr+s, tc+s-1, s);
    }
    
    if(dr>=tr+s && dc>=tc+s)//右下角區域
        chessBoard(tr+s, tc+s, dr, dc, s);
    else
    {
        board[tr+s][tc+s]=t;//區域左下賦t值
        chessBoard(tr+s, tc+s, tr+s, tc+s, s);
    }
    //每執行一遍就相當與往上面填上了個圖形。
}
 
int  main()
{
    int size;
    printf("輸入棋盤的size(大小必須是2的n次幂): ");
    scanf("%d",&size);
    int index_x,index_y;
    printf("輸入特殊方格位置的坐标: ");
    scanf("%d %d",&index_x,&index_y);
    chessBoard(0,0,index_x,index_y,size);
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
            printf("%4d",board[i][j]);
        printf("\n");
    }
    return 0;
}