ChessBoardボードオーバーライドの問題


碁盤カバー問題は古典的な分治問題のアルゴリズムであり、その中の思想は、分而治之である.
どのように分けて治める思想を体現するかがこの問題の鍵である.
まず、碁盤を4つの小さなブロックに分けて、分を体現していますが、問題の統一性を破壊しました.小さなブロックの中で、3つのブロックには特殊なブロックがありませんから.
だから、分を破壊しないで乱れない思想のために、私达はすべての小さい塊の中で1つの特殊な小さい塊を加えることができて、しかし1つの小さい塊をプラスして、勝手に記入すると、同じようにやはり分の目的を破壊して、だから、本の上で1种の比较的に上手な技巧を提供して、特殊な塊のないブロックの中で、1つのL型の塊を3つの塊の境のところに置いて、1つのこれは碁盤にブロックを埋める方法で、題意を破壊しない目的であり、二つ目は、他の3つの特殊なブロックのない四角形、3つの特殊な四角形を追加した.一石二鳥ともいえるように、別れた後の問題は元の問題と同じで、それだけが分治法で処理できる.
次のコードは同じで、c++コードを使用しています.
         
//     
#include<iostream>
#include<cstring>
#include<cstdlib>
#define SIZE 8
using namespace std;
int Board[SIZE][SIZE];//     
int kind;             //       
void ChessBoard(int tr,int tc,int dr,int dc,int size){
    if(size==1)return;
    int t=kind++;
    int s=size/2;
    //             
    if(dr < tr + s&&dc < tc + s)//       ,      
    ChessBoard(tr,tc,dr,dc,s);
    else{                       //        ,              
        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;
        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;
        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;
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
        }
    }
    
int main(){
    memset(Board,0,sizeof(Board));//      0 
    cout<<"Initnation the Board!The curent sutation is:"<<endl;
    for(int i = 0;i < SIZE;i ++){
        for(int j = 0;j < SIZE;j ++)
        cout<<Board[i][j]<<" ";
        cout<<endl;
        }                          //          
    cout<<"The chessboard is covered..."<<endl;
    ChessBoard(0,0,0,3,SIZE);       //     
    cout<<"The chessboard is:"<<endl;
    cout.fill('0');                 // 0     
    for(int i = 0;i < SIZE;i ++){
        for(int j = 0;j < SIZE;j ++){
        cout.width(2);              //                 
        cout<<Board[i][j]<<" ";
        }
        cout<<endl;
        }
        system("pause");
    }