当前位置 博文首页 > 爱新觉罗?炒饭的博客:棋盘覆盖(分治法+递归)
题意及思路如下图:
代码如下:
#include <iostream>
#include <cstdlib>
#include <string.h>
using namespace std;
int tile=1;
int Board[100][100];
/*
* tr : 棋盘左上角顶点的行号,tc棋盘左上角顶点的列号
* dr : 特殊方格左上角顶点的行号,dc特殊方格左上角顶点的列号
* size :size = 2^k 棋盘规格为2^k*2^k
*/
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
if(size==1)
return;
int t=tile++;
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; //将t号L型骨牌覆盖当前子棋盘左下角的方格
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号L型骨牌覆盖当前子棋盘左下角的方格
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号L型骨牌覆盖当前子棋盘左上角的方格
ChessBoard(tr+s,tc+s,tr+s,tc+s,s); //对右下角棋盘继续进行递归划分覆盖
}
}
int main()
{
int size,x,y;
cout<<"请输入棋盘的规格:"<<endl;
cin>>size;
cout<<"请输入特殊方格的位置:"<<endl;
cin>>x>>y;
memset(Board,0,sizeof(Board));
ChessBoard(0,0,x,y,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
cout<<Board[i][j]<<" ";
cout<<endl;
}
system("pause");
return 0;
}
cs