青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

alpc60 ACM/ICPC程序設計
成長的路……源
posts - 20,comments - 42,trackbacks - 0

The Rotation Game

Time Limit: 15000MS

 

Memory Limit: 150000K

Total Submissions: 944

 

Accepted: 218

Description

The rotation game uses a # shaped board, which can hold 24 pieces of square blocks (see Fig.1). The blocks are marked with symbols 1, 2 and 3, with exactly 8 pieces of each kind.


Initially, the blocks are placed on the board randomly. Your task is to move the blocks so that the eight blocks placed in the center square have the same symbol marked. There is only one type of valid move, which is to rotate one of the four lines, each consisting of seven blocks. That is, six blocks in the line are moved towards the head by one block and the head block is moved to the end of the line. The eight possible moves are marked with capital letters A to H. Figure 1 illustrates two consecutive moves, move A and move C from some initial configuration.

Input

The input consists of no more than 30 test cases. Each test case has only one line that contains 24 numbers, which are the symbols of the blocks in the initial configuration. The rows of blocks are listed from top to bottom. For each row the blocks are listed from left to right. The numbers are separated by spaces. For example, the first test case in the sample input corresponds to the initial configuration in Fig.1. There are no blank lines between cases. There is a line containing a single `0' after the last test case that ends the input.

Output

For each test case, you must output two lines. The first line contains all the moves needed to reach the final configuration. Each move is a letter, ranging from `A' to `H', and there should not be any spaces between the letters in the line. If no moves are needed, output `No moves needed' instead. In the second line, you must output the symbol of the blocks in the center square after these moves. If there are several possible solutions, you must output the one that uses the least number of moves. If there is still more than one possible solution, you must output the solution that is smallest in dictionary order for the letters of the moves. There is no need to output blank lines between cases.

Sample Input

1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
0

Sample Output

AC
2
DDHH
2

Source

Shanghai 2004

 

 

圖中的#字格的4條豎線,可以按8個方向倒轉里面的數字方塊,當中間的8個數字方塊是同一個數字時,游戲結束。這道題就要求搜索一個最短路徑,倒轉8個方向使得中間8個數字相等。這道題目看起來很像一道單純的BFS,看了POJ里面說BFS會爆內存,我沒試,估計寫得好的也爆不了。但是估計寫BFS還要涉及到狀態的判重,程序寫起來也不方便。我用了迭代加深的搜索方法。第一次接觸這個算法,我說一下我的理解:

       原來我很不理解迭代加深,搜索的深度一層一層地加,在后面的某一深度限制下搜索,必定會搜到前面深度所能搜到的結果,這會造成重復搜索。基于這點,我一直都認為迭代加深搜索的方法很冗余,當然也是自己從來都沒有動手試過。像這道題就給我的收獲不少,有的時候選擇一定的策略進行搜索,我們是很難確定解所在狀態空間的深度的,有時可能解的深度不大,但整個狀態空間的深度很大,盲目的dfs搜索在狀態空間里就有可能會越陷越深,遲遲出不了解,同時整個狀態空間的寬度也很大,用BFS可能就會爆空間。迭代加深搜索恰恰是取了一個折中。利用了dfs的優勢,限制了搜索的深度,避免了出現無解的境地。由于深度是逐個增加的,當搜到一個解后就退出,所以避免了BFS中判重的一步操作,當然在迭代深搜的過程中,還可以加入剪枝,可以優化程序。但是我的程序在POJ上還不快,還要找找原因,也許還有優化。下面是一些關鍵代碼:


for(limit=0; ;limit++)
        
{
            
if(dfs(start,0))
            
{
                
if(limit == 0)
                
{
                    printf(
"No moves needed\n");
                }

                
else
                
{
                    
for(i=0; i<limit; i++)
                    
{
                        printf(
"%c",'A'+pre[i]);
                    }

                    printf(
"\n");
                }

                printf(
"%d\n",rlt);
                
break;
            }

        }

///迭代過程
int dfs(struct S now, int depth)
{
    
int c1,c2,c3;
    struct S st;
    test(now,c1,c2,c3);
    
if(c1 == 8)
    
{
        rlt
=1;
        
return 1;
    }

    
else if(c2 == 8)
    
{
        rlt
=2;
        
return 1;
    }

    
else if(c3 == 8)
    
{
        rlt
=3;
        
return 1;
    }

    
if(depth == limit)
        
return 0;
    
if(8-c1 > limit-depth && 8-c2 > limit-depth && 8-c3 > limit-depth)
        
return 0;
    st
=NewStateA(now);
    pre[depth]
=0;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateB(now);
    pre[depth]
=1;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateC(now);
    pre[depth]
=2;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateD(now);
    pre[depth]
=3;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateE(now);
    pre[depth]
=4;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateF(now);
    pre[depth]
=5;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateG(now);
    pre[depth]
=6;
    
if(dfs(st,depth+1))
        
return 1;
    st
=NewStateH(now);
    pre[depth]
=7;
    
if(dfs(st,depth+1))
        
return 1;
    
return 0;
}

///深搜
posted on 2008-04-20 15:44 飛飛 閱讀(2722) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC

FeedBack:
# re: 迭代加深搜索
2008-07-04 20:08 | wzc1989
謝謝大牛分享!!!  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲免费在线电影| 欧美国产欧美亚洲国产日韩mv天天看完整 | 欧美精品色一区二区三区| 亚洲观看高清完整版在线观看| 久久手机精品视频| 久久亚洲精品视频| 亚洲精品激情| 9i看片成人免费高清| 国产精品美女久久久| 久久精品国产v日韩v亚洲| 欧美一区在线看| 亚洲激情小视频| 一本色道久久综合一区| 国产日本欧美一区二区| 美女脱光内衣内裤视频久久网站| 蜜桃av一区二区| 中国女人久久久| 久久都是精品| 这里只有精品丝袜| 久久成人精品无人区| 亚洲精品少妇30p| 午夜精品国产| 亚洲麻豆视频| 欧美在线999| 一区二区三区回区在观看免费视频| 午夜精品久久久久久久久久久久久| 亚洲大片免费看| 亚洲一区二区三区精品视频| 亚洲国产欧美在线人成| 亚洲一区国产视频| 亚洲人成在线观看网站高清| 亚洲欧美日韩国产成人| 日韩视频中文字幕| 久久青草欧美一区二区三区| 亚洲男人天堂2024| 欧美成年人网站| 久久婷婷综合激情| 国产精品捆绑调教| 亚洲国产视频直播| 国产偷久久久精品专区| 日韩视频精品在线观看| 亚洲国产高潮在线观看| 欧美一区二区三区久久精品| 亚洲一级电影| 欧美另类视频在线| 欧美激情视频在线播放| 国模叶桐国产精品一区| 亚洲欧美春色| 午夜精彩视频在线观看不卡| 欧美日产在线观看| 亚洲国产福利在线| 亚洲高清资源| 老司机精品视频一区二区三区| 久久电影一区| 国产欧美精品日韩| 亚洲欧美清纯在线制服| 午夜精品福利在线| 国产精品久久国产三级国电话系列| 亚洲精品在线观| 99精品视频免费观看视频| 牛夜精品久久久久久久99黑人| 免费成人av在线| 在线播放日韩专区| 美女露胸一区二区三区| 欧美激情区在线播放| 91久久在线播放| 欧美高清不卡在线| 亚洲三级毛片| 亚洲午夜未删减在线观看| 欧美肉体xxxx裸体137大胆| 一区二区三区四区五区精品视频| 亚洲性图久久| 国产精品视频一二| 欧美一级专区免费大片| 久热精品视频在线免费观看| 影音先锋亚洲视频| 欧美电影专区| 久久精品av麻豆的观看方式| 久久国产精彩视频| 亚洲在线播放电影| 久久国产精品色婷婷| 亚洲社区在线观看| 国产精品99久久不卡二区| 亚洲国产成人久久综合| 欧美韩日一区| 91久久精品日日躁夜夜躁国产| 麻豆精品精品国产自在97香蕉| 亚洲国产精品悠悠久久琪琪| 亚洲欧美美女| 亚洲经典自拍| 国产精品卡一卡二卡三| 久久精品夜色噜噜亚洲aⅴ| 伊人久久av导航| 免费影视亚洲| 亚洲天堂av综合网| 美女黄网久久| 亚洲一区三区视频在线观看| 黄色欧美日韩| 欧美精品一区二区三区高清aⅴ| 在线综合亚洲| 欧美激情91| 欧美在线三级| 一本久久综合亚洲鲁鲁| 国产真实久久| 欧美日韩一区二区免费视频| 欧美专区亚洲专区| 一本大道久久a久久综合婷婷| 久久久精品国产免大香伊| 亚洲最新在线| 在线免费不卡视频| 国产精品视频一区二区三区 | 亚洲欧洲在线一区| 国产视频久久久久久久| 欧美激情一区二区三区四区| 欧美一区二区三区四区在线| 亚洲免费黄色| 欧美激情一区三区| 久久久精品一区二区三区| 亚洲网在线观看| 亚洲精品在线三区| 狠狠综合久久av一区二区老牛| 欧美日韩亚洲一区二区三区四区 | 国产精品久久久久77777| 欧美成人精品| 久久一区二区视频| 小黄鸭精品aⅴ导航网站入口| 日韩一区二区精品葵司在线| 欧美激情一区二区三区在线视频| 久久久久久免费| 久久福利影视| 亚洲免费在线播放| 亚洲永久精品国产| 亚洲私人影院| 中文av字幕一区| 中文国产一区| 中文一区二区| 一区二区三区四区在线| 一本不卡影院| 这里只有精品视频在线| 一区二区日韩免费看| 一区二区三区 在线观看视频| 99成人精品| 宅男精品导航| 亚洲欧美日韩综合| 午夜久久99| 久久国产精品久久久久久| 欧美在线黄色| 蜜臀av性久久久久蜜臀aⅴ四虎| 久久在线视频| 欧美国产欧美亚州国产日韩mv天天看完整| 久久亚洲精品视频| 欧美福利专区| 亚洲精品一区二区三区樱花| 日韩一级黄色大片| 亚洲一区久久| 久久久久高清| 欧美金8天国| 国产精品多人| 国内成人精品2018免费看| 极品av少妇一区二区| 亚洲精品久久7777| 亚洲一区二区少妇| 久久精品国产99国产精品| 美女露胸一区二区三区| 亚洲欧洲日本一区二区三区| 99v久久综合狠狠综合久久| 亚洲欧美日韩在线综合| 久久综合色影院| 国产精品成人一区二区三区夜夜夜| 国产精自产拍久久久久久蜜| 悠悠资源网亚洲青| 在线亚洲美日韩| 久久久久久久综合狠狠综合| 欧美国产日韩免费| 亚洲一区二区三区免费在线观看| 久久精品99久久香蕉国产色戒| 欧美成人精品三级在线观看| 国产精品美女久久久久aⅴ国产馆| 狠狠色丁香久久综合频道| 亚洲精品国精品久久99热一| 欧美一区二区三区另类| 亚洲福利视频网| 亚洲欧美日韩精品综合在线观看| 老鸭窝91久久精品色噜噜导演| 欧美色网在线| 亚洲欧洲精品一区二区三区| 性欧美超级视频| 亚洲人成网站在线播| 久久xxxx精品视频| 国产精品成人观看视频免费 | 国产婷婷色一区二区三区四区| 亚洲精品一区二区三| 久久琪琪电影院| 一区二区三区精品久久久| 免费国产一区二区| 国产一区二区三区av电影| 亚洲女人天堂av| 亚洲三级国产| 欧美激情久久久| 亚洲国产天堂久久综合网|