jake1036

分治法 之 棋盘分割问题

/*
该算法适宜使用分治法解决 
(1) 含有4的k次方个方格的棋盘。
(2) 在其中的一个方格中有一个特殊的棋子，现在打算将L型的骨牌覆盖到棋盘中。
(3) 要求除了那一个特殊的棋子之外，其余的格子均可以由L型骨牌覆盖。 
 
 
解决方法:
(1) 将整个棋盘等分成4块 ，每块2的(k-1)次方个棋格。
(2) 判断每一个小的棋盘， 若特殊棋子在这个小棋盘中，则按相同的方法递归处理这个小棋盘。
(3) 若这个小棋盘中不存在 特殊棋子，则就根据该棋盘的位置，来分别进行处理。

(4) 若该棋盘在原来棋盘的左上，则在小棋盘的右下方设置一个特殊字符。
(5) 若该棋盘在原来棋盘的右上，则在小棋盘的左下方设置一个特殊字符。
(6) 若该棋盘在原来棋盘的左下，则在小棋盘的右上方设置一个特殊字符。
(7) 若该棋盘在原来棋盘的右下，则在小棋盘的左上方设置一个特殊字符。       
    
经过4 , 5 , 6 ,7各个步骤，则 各个子问题 转换为 与 原问题相同的问题。 
 
*/

#include <stdio.h>

#define M 8 
  int tile = 1 ;  //表示当前的纸牌编号 
  int board [M][M] ;   

 /*
    tr 棋盘左上角的行坐标 
    tc 棋盘左上角的列坐标 
    dr 特殊棋子的行坐标 
    dc 特殊棋子的列坐标 
  */
 void chessBoard(int tr , int tc , int dr , int dc , int size)
 {
    if(size == 1) //递归结束条件  
        return ;
      
    int t = tile++ , s = size / 2; //t表示当前的纸牌号 , s表示当前的棋盘大小的一半 
    
    //当特殊的棋子在左上角的小棋盘中  
      if(dr < tr + s && dc < tc + s)
        chessBoard(tr , tc , dr , dc , s) ;
      else  //如果不在左上角小棋盘的话,则把当前该小棋盘的右下角置位一个特殊字符
      {
        board[tr + s -1][tc + s - 1] = t ; //赋值为编号为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 - 1 && 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) ;   
    }
        
 } 


 int main()
 {
     chessBoard(0,0,2 ,3 ,M) ;
     for(int i = 0 ; i < M ; i++)
       for(int j = 0 ; j < M ; j++)
         {
           printf("%d  " , board[i][j]) ;
           if(j == (M-1))
            printf("\n") ;
         }
    getchar() ;
     return 0 ;     
 }



 

posted on 2010-12-07 20:25 kahn 阅读(1098) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理