0001-算法笔记分治法实现棋盘覆盖问题

今天上课老师讲了分治法，下课后自己把程序碼了一遍，还是存在一个疑问--为什么每个方格都会填充到，在下面将会解决并叙述。

        首先贴上程序：

#include <stdio.h>
 #include <stdlib.h>
 #include <memory.h>
 int tile = 0;
 int Board[100][100];

 /*    tr:棋盘左上角方格的行号
    tc:棋盘左上角方格的列号
    dr:特殊方格所在行号
    dt:特殊方格所在列号
*/
 void chessBoard(int tr, int tc, int dr, int dc, int size);


 int main()
 {
     int size,r,c,row,col;
     memset(Board,0,sizeof(Board));
     scanf("%d",&size);
     scanf("%d%d",&row,&col);
     chessBoard(0,0,row,col,size);


     for (r = 0; r < size; r++)
     {
         for (c = 0; c < size; c++)
         {
             printf("%2d ",Board[r][c]);
         }
         printf("\n");
     }


     return 0;
 }

void chessBoard(int tr, int tc, int dr, int dc, int size)
 {
     int s,t;
     if (1 == size) return;


     s = size/2;               //分割棋盘 
     t = ++ tile;              //L型骨牌号

     //覆盖左上角子棋盘
     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+s,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
     {
         Board[tr+s][tc+s] = t;
         chessBoard(tr+s,tc+s,tr+s,tc+s,s);
     }


 }

实现结果如图示:

通过代码调试，我们可以看到，每次的填值都是将方格里的值填入，而不是只填特殊格的值。书中的这段代码在每次覆盖还有循环递归中也设计的很巧妙！和大家一起分享学习