分治算法——棋盘覆盖

//算法思想：当k=0时，及特殊方格，骨牌数为1.
//当k>0时，将2的k次方*2的k次方棋盘划分为4个较小的棋盘，而其余三个子棋盘中无特殊方格。
//继续递归成4个较小的棋盘。
//用L型骨牌覆盖在3个子棋盘汇合处。
int tile = 1;
int Board[8][8];
void ChessBoard(int tr, int tc, int dr, int dc, int size) {
  //tr棋盘左上角方格的行号
  //tc棋盘左上角方格的列号
  //dr特殊方格的行号
  //dc特殊方格的列号
  //size 棋盘规模2的k次方
  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;//如果不含有特殊格子，将棋盘右下角覆盖特殊骨牌。
    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);//递归的时候修改特殊格子的位置。
  }
}