棋盘覆盖.cpp

这是学习动态规划时用动态规划设计分析实际问题

#include"iostream"
using namespace std;
int tile=0;
const int SIZE=8;
int board[SIZE][SIZE];

void chessBoard(int tr,int tc,int dr,int dc,int size)
{
 if(size==1)return ;
 
 int t=tile++,s=size/2;//t为L型骨牌号,S分割棋盘
 //覆盖左上角子棋盘
 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(int argc, char* argv[])
{
 int dr,dc;int tr=1;int tc=1;
 int i,j; 
 cout<<endl<<"输入dr,dc:"<<endl;
 cin>>dr>>dc;
 chessBoard(tr,tc,dr,dc,SIZE);
   for(i=0;i<SIZE;i++)
   
   {
	   cout<<endl;
	   for(j=0;j<SIZE;j++)
		  printf("%4d",board[i+tr][j+tc]) ;
   }
   cout<<endl;
    return 0;
}