ChessBoardボードオーバーライドの問題
碁盤カバー問題は古典的な分治問題のアルゴリズムであり、その中の思想は、分而治之である.
どのように分けて治める思想を体現するかがこの問題の鍵である.
まず、碁盤を4つの小さなブロックに分けて、分を体現していますが、問題の統一性を破壊しました.小さなブロックの中で、3つのブロックには特殊なブロックがありませんから.
だから、分を破壊しないで乱れない思想のために、私达はすべての小さい塊の中で1つの特殊な小さい塊を加えることができて、しかし1つの小さい塊をプラスして、勝手に記入すると、同じようにやはり分の目的を破壊して、だから、本の上で1种の比较的に上手な技巧を提供して、特殊な塊のないブロックの中で、1つのL型の塊を3つの塊の境のところに置いて、1つのこれは碁盤にブロックを埋める方法で、題意を破壊しない目的であり、二つ目は、他の3つの特殊なブロックのない四角形、3つの特殊な四角形を追加した.一石二鳥ともいえるように、別れた後の問題は元の問題と同じで、それだけが分治法で処理できる.
次のコードは同じで、c++コードを使用しています.
どのように分けて治める思想を体現するかがこの問題の鍵である.
まず、碁盤を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");
}