棋盘覆盖问题 分治法

#include<iostream> #include<math.h> using namespace std; int Board[105][105]; static int tile=1; void ChessBoard(int tr,int tc,int dr,int dc,int size) { if(size==1) return; int t=tile++;//L型骨牌号 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;//用t号L型骨牌覆盖右下角（该棋盘的特殊方格） 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,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() { int k; while(cin>>k)//2^k*2^k的方格 { int size=pow(2,k)*pow(2,k); int x,y; cin>>x>>y;//特殊方格的坐标 Board[x][y]=0; ChessBoard(0,0,x,y,size); for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { cout<<Board[i][j]<<"\t"; } cout<<endl; } } return 0; }