棋盤覆蓋問題算法

#include<stdio.h>
int tile=1;
int board[100][100];
 //可以用一個二維數(shù)組board[size][size]表示一個棋盤，其中弟断，size=2^k般甲。這里設置成100，來容納棋盤 
 //為了在遞歸處理的過程中使用同一個棋盤禽作，將數(shù)組board設為全局變量缨该；
void ChessBoard(int tr,int tc,int dr,int dc,int size) 
//子棋盤由棋盤左上角的下標tr勤晚、tc和棋盤大小s表示似嗤；
//用board[dr][dc]表示特殊方格啸臀，dr和dc是該特殊方格在二維數(shù)組board中的下標;
{
    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  
        {   
            //此棋盤中無特殊方格 ,用t號L型骨牌覆蓋右下角  
            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,dr,dc,s);  
         else  
         {
            //特此棋盤中無特殊方格 ,t號L型骨牌覆蓋左下角  
            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  
         {
            //此棋盤中無特殊方格 ,t號L型骨牌覆蓋右上角  
            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  
         {
            //此棋盤中無特殊方格 ,t號L型骨牌覆蓋左上角  
            board[tr+s][tc+s]=t;  
            //覆蓋本子棋盤中的其余方格  
            ChessBoard(tr+s,tc+s,tr+s,tc+s,s);  
         }         
}  
int main()      
{  
    int size,r,c,row,col;  
    printf("輸入棋盤大小：\n");  
    scanf("%d",&size);//輸入棋盤大小  
    printf("輸入特殊方格位置：row,col\n");  
    scanf("%d,%d",&row,&col);//輸入特殊方格位置  
    ChessBoard(0,0,row,col,size);  
    printf("輸出棋盤覆蓋結(jié)果：\n");  
    for (r = 0; r < size; r++)//輸出棋盤覆蓋結(jié)果  
    {  
       for (c = 0; c < size; c++)  
       {  
       printf("%-4d ",board[r][c]);  
       }  
       printf("\n");  
    }  
        return 0;  
}  

運行效果