Liny_@NotePad

沉迷ACG中

分治法：棋盘覆盖问题

YOYO posted @ 2009年4月29日 08:05 in 【算法】与【数据结构】 with tags 分治 , 3332 阅读

若棋盘规格是1*1，则不用填充；
若棋盘规格大于1*1，则将棋盘分割成四个子棋盘。判断特殊点在哪一个子棋盘中，进入该棋盘继续覆盖，而对其他子棋盘，设置边界点为新特殊点（填充这3个边界点即是填充了一个L型骨牌），并对各个子棋盘继续覆盖。

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 10        //  最大棋盘size
  5.  
  6. int Board[N][N];        //      棋盘矩阵
  7. int tile = 1;      // 当前骨牌编号
  8.  
  9. /**************************************************************
  10. * 棋盘覆盖分治算法
  11. *
  12. * 输入：棋盘起始点坐标tr,tc，特殊点坐标dr,dc，棋盘规格小size
  13. * 输出：覆盖好的棋盘矩阵Board[][]
  14. **************************************************************/
  15. void ChessBoard(int tr, int tc, int dr, int dc, int size){
  16.         if(size==1)return;            //    若棋盘大小为1则返回
  17.         int t = tile++,   //       当前要填充的骨牌号
  18.                 s = size/2;               //   分割的棋盘规格
  19.  
  20.         //      若特殊点在左上角棋盘
  21.         if(dr<tr+s&&dc<tc+s){
  22.                 //      特殊方格在此棋盘中
  23.                 ChessBoard(tr,tc,dr,dc,s);
  24.         }else{
  25.                 //      将该棋盘的右下角点填充骨牌，使其成为新特殊点
  26.                 Board[tr+s-1][tc+s-1] = t;
  27.                 //      在该棋盘中继续覆盖
  28.                 ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
  29.         }
  30.  
  31.         //      若特殊点在右上角棋盘
  32.         if(dr<tr+s&&dc>=tc+s){
  33.                 ChessBoard(tr, tc+s, dr, dc, s);
  34.         }else{
  35.                 Board[tr+s-1][tc+s] = t;
  36.                 ChessBoard(tr, tc+s, tr+s-1, tc+s, s);
  37.         }
  38.  
  39.         //      若特殊点在左下角棋盘
  40.         if(dr>=tr+s&&dc<tc+s){
  41.                 ChessBoard(tr+s, tc, dr, dc, s);
  42.         }else{
  43.                 Board[tr+s][tc+s-1]= t;
  44.                 ChessBoard(tr+s, tc, tr+s, tc+s-1, s);
  45.         }
  46.  
  47.         //      若特殊点在右下角棋盘
  48.         if(dr>=tr+s&&dc>=tc+s){
  49.                 ChessBoard(tr+s, tc+s, dr, dc, s);
  50.         }else{
  51.                 Board[tr+s][tc+s] = t;
  52.                 ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
  53.         }
  54. }
  55.  
  56. int main(){
  57.         int n,i,j,x,y;
  58.  
  59.         //      输入棋盘规格和特殊点坐标x,y
  60.         cin>>n>>x>>y;
  61.  
  62.         //      初始化棋盘矩阵
  63.         memset(Board,0,sizeof(Board));
  64.        
  65.         //      覆盖棋盘
  66.         ChessBoard(0,0,x,y,n);
  67.  
  68.         //      输出覆盖后的棋盘矩阵
  69.         for(i=0;i<n;i++){
  70.                 for(j=0;j<n;j++){
  71.                         printf("%5d",Board[i][j]);
  72.                 }
  73.                 cout<<endl;
  74.         }
  75.  
  76.         return 0;
  77. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter