2017-08-26 20:18:50

writer：pprp

问题大概描述：

有一个2k∗2k的方格棋盘，恰有一个方格是黑色的，其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。

黑色方格不能被覆盖，且任意一个白色方格不能同时被两个或更多牌覆盖。

用分治法来解决，分治的时候要确定状态，需要什么状态，结束条件

结束条件是size规模变成了1的时候，就要退出了；

需要的状态，起始点，黑色块的位置，size边长

/*@theme:棋盘用L型的块堆满@writer:pprp@declare:最经典的分治算法@date:2017/8/26*/#include 
     
      #include 
      
       using namespace std;const int maxn = 10000;int chess[maxn][maxn];int number;void chessBoard(int row, int column, int x, int y, int Size){       if(Size == 1) return ;//退出条件       int ss = Size/2;//分治，规模减半              int t = ++number;       int centerRow = row + ss;       int centerColumn = column + ss;              //开始判断四个方向       //左上角判断       if(x < centerRow && y < centerColumn)       {             chessBoard(row,column,x,y,ss);       }       else       {             chess[centerRow-1][centerColumn-1] = t;             chessBoard(row,column,centerRow-1,centerColumn-1,ss);       }              //右上角判断       if(x < centerRow && y >= centerColumn)       {             chessBoard(row,centerColumn,x,y,ss);       }       else       {             chess[centerRow-1][centerColumn] = t;             chessBoard(row,centerColumn,centerRow-1,centerColumn,ss);       }              //左下角判断       if(x >= centerRow && y < centerColumn)       {             chessBoard(centerRow,column,x,y,ss);       }       else       {             chess[centerRow][centerColumn-1] = t;             chessBoard(centerRow,column,centerRow,centerColumn-1,ss);       }                                                                                 //右下角判断       if(x >= centerRow && y >= centerColumn)       {             chessBoard(centerRow,centerColumn,x,y,ss);       }       else       {             chess[centerRow][centerColumn] = t;             chessBoard(centerRow,centerColumn,centerRow,centerColumn,ss);       }       }int main(){      int Size;      int x, y;      while(cin >> Size && Size)      {            memset(chess, 0, sizeof(chess));            cin >> x >> y;            chessBoard(0,0,x,y,Size);                 chess[x][y] = number = 1;                                for(int i = 0 ; i < Size; i++)            {                  for(int j = 0 ; j < Size ; j++)                  {                        cout << chess[i][j]<< "\t";                  }                  cout << endl << endl;;            }      }                  return 0;}