• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            jake1036
            

            

            



            
	
					
	
            
		
            
			分治法 之 棋盤分割問題
		
            
		
            /*
            該算法適宜使用分治法解決 
            (1) 含有4的k次方個(gè)方格的棋盤。
            (2) 在其中的一個(gè)方格中有一個(gè)特殊的棋子，現(xiàn)在打算將L型的骨牌覆蓋到棋盤中。
            (3) 要求除了那一個(gè)特殊的棋子之外，其余的格子均可以由L型骨牌覆蓋。 
             
             
            解決方法:
            (1) 將整個(gè)棋盤等分成4塊 ，每塊2的(k-1)次方個(gè)棋格。
            (2) 判斷每一個(gè)小的棋盤， 若特殊棋子在這個(gè)小棋盤中，則按相同的方法遞歸處理這個(gè)小棋盤。
            (3) 若這個(gè)小棋盤中不存在 特殊棋子，則就根據(jù)該棋盤的位置，來分別進(jìn)行處理。

            (4) 若該棋盤在原來棋盤的左上，則在小棋盤的右下方設(shè)置一個(gè)特殊字符。
            (5) 若該棋盤在原來棋盤的右上，則在小棋盤的左下方設(shè)置一個(gè)特殊字符。
            (6) 若該棋盤在原來棋盤的左下，則在小棋盤的右上方設(shè)置一個(gè)特殊字符。
            (7) 若該棋盤在原來棋盤的右下，則在小棋盤的左上方設(shè)置一個(gè)特殊字符。       
                
            經(jīng)過4 , 5 , 6 ,7各個(gè)步驟，則 各個(gè)子問題 轉(zhuǎn)換為 與 原問題相同的問題。 
             
            */

            #include             <stdio.h>

            #define M 8 
                          int tile = 1 ;  //表示當(dāng)前的紙牌編號 
              int board [M][M] ;   

                         /*
                tr 棋盤左上角的行坐標(biāo) 
                tc 棋盤左上角的列坐標(biāo) 
                dr 特殊棋子的行坐標(biāo) 
                dc 特殊棋子的列坐標(biāo) 
                          */
                         void chessBoard(int tr , int tc , int dr , int dc , int size)
                         {
                            if(size == 1) //遞歸結(jié)束條件  
                    return ;
                  
                            int t = tile++ , s = size / 2; //t表示當(dāng)前的紙牌號 , s表示當(dāng)前的棋盤大小的一半 
                
                            //當(dāng)特殊的棋子在左上角的小棋盤中  
                  if(dr < tr + s && dc < tc + s)
                    chessBoard(tr , tc , dr , dc , s) ;
                              else  //如果不在左上角小棋盤的話,則把當(dāng)前該小棋盤的右下角置位一個(gè)特殊字符
                  {
                    board[tr             + s -1][tc + s - 1] = t ; //賦值為編號為t的字牌     
                    chessBoard(tr , tc , tr + s - 1 , tc + s - 1 , s) ; 
                  }
                            //當(dāng)特殊的棋子在右上角的小棋盤中
                 if(dr < tr + s && dc >= tc + s)
                   chessBoard(tr , tc             + s  , dr , dc , s) ;
                              else  //如果不在右上角的棋盤中，則把當(dāng)前該棋盤的左下角置位為一個(gè)特殊字符 
                  {
                      board[tr             + s - 1][ tc + s] = t ;
                      chessBoard(tr , tc             + s , tr + s - 1 , tc + s , s) ; 
                      
                  }
                  
                            //當(dāng)特殊的棋子在左下角的棋盤中
                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) ;
                 }             
                  
                            //當(dāng)特殊的棋子在右下角的棋盤中
                if(dr >= tr + s && dc >= tc + s )
                  chessBoard(tr             + s , tc + s  , dr , dc , s) ;
                            else  //當(dāng)不在該子棋盤中的時(shí)候，則在子棋盤的左上角設(shè)置一個(gè)特殊棋子 
                {    
                   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 閱讀(1122) 評論(0)  編輯 收藏 引用  所屬分類: 算法相關(guān) 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



少妇久久久久久被弄高潮|
久久夜色精品国产亚洲|
久久久无码精品亚洲日韩蜜臀浪潮|
久久受www免费人成_看片中文|
久久久无码精品亚洲日韩按摩
|
国产精品丝袜久久久久久不卡
|
久久综合九色综合欧美就去吻
|
久久夜色精品国产亚洲|
国产精品99久久久精品无码|
国内精品久久九九国产精品|
日韩一区二区三区视频久久|
久久91综合国产91久久精品
|
婷婷综合久久狠狠色99h|
日本久久中文字幕|
久久青青草原国产精品免费|
久久人人爽人人爽人人av东京热
|
777午夜精品久久av蜜臀|
国产精品久久久天天影视香蕉|
久久婷婷五月综合国产尤物app
|
亚洲va久久久噜噜噜久久狠狠|
精品久久久无码中文字幕|
韩国免费A级毛片久久|
久久国语露脸国产精品电影|
日韩欧美亚洲综合久久影院Ds|
久久精品国产半推半就|
国内精品久久久久久99蜜桃|
综合人妻久久一区二区精品|
精品人妻伦九区久久AAA片69|
开心久久婷婷综合中文字幕|
久久精品国产72国产精福利|
国产精品激情综合久久|
精品国产乱码久久久久久浪潮|
日本久久久久久中文字幕|
成人久久综合网|
亚洲一区二区三区日本久久九|
aaa级精品久久久国产片|
久久精品草草草|
久久se精品一区二区影院
|
久久丫忘忧草产品|
无码超乳爆乳中文字幕久久|
久久99国内精品自在现线|