棋盘覆盖问题.txt

个人笔记 适合初学者 josephus小孩围圈问题 二分搜索 活动安排问题

void chessboard(int tr,int tc,int dr,int dc,int size)
{
   if(size==1) return;
   int t=tile++,     //L型骨牌号
      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+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{  //此棋盘中无特殊方格
       //用t号L型骨牌覆盖左上角
       board[tr+s][tc+s]=t;
       //覆盖其余方格
       chessboard(tr+s,tc+s,tr+s,tc+s,s);}
}
上述算法中，用一个二维整形数组board表示棋盘。board[0][0]是棋盘的左上角方格。
tile是算法中的一个全局整形变量，用来表示L型骨牌的编号，其初值为0。
算法的输入参数是：
tr:棋盘左上角方格的行号；
tc:棋盘左上角方格的列号；
dr:特殊方格所在的行号；
dc:特殊方格所在的列号；
size:size=2^k,