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

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>
            久久久久女教师免费一区| 欧美国产亚洲另类动漫| 国产精品丝袜久久久久久app| 洋洋av久久久久久久一区| 亚洲丁香婷深爱综合| 欧美激情四色| 亚洲一区二区三区午夜| 欧美在线欧美在线| 亚洲激情在线| 亚洲线精品一区二区三区八戒| 国产欧美精品日韩区二区麻豆天美| 久久精品二区亚洲w码| 久久这里只有| 午夜精品在线观看| 久久综合久久综合久久综合| 一区二区欧美国产| 羞羞色国产精品| 亚洲毛片网站| 午夜精品美女自拍福到在线| 亚洲国产成人一区| 国产精品99久久久久久久vr | 欧美国产精品劲爆| 国产精品v片在线观看不卡| 久久激情久久| 欧美精品v日韩精品v国产精品| 小辣椒精品导航| 欧美成人免费网| 久久经典综合| 欧美日韩亚洲一区| 免费不卡在线视频| 国产精品一二| 日韩视频在线播放| 亚洲人成网站色ww在线| 亚洲永久精品国产| 亚洲私人黄色宅男| 老司机一区二区| 久久久久久网站| 国产精品久久久久天堂| 亚洲人成在线影院| 亚洲精品老司机| 激情综合久久| 亚洲欧美日韩一区在线| 亚洲小说区图片区| 欧美国产第二页| 欧美成人精品福利| 激情婷婷欧美| 久久精品成人一区二区三区| 亚洲欧美日韩国产一区二区三区| 欧美激情偷拍| 91久久午夜| 91久久精品国产91久久性色tv| 久久精品人人做人人综合 | 国内久久婷婷综合| 亚洲综合色自拍一区| 亚洲视频导航| 欧美日韩亚洲一区三区| 免费观看亚洲视频大全| 国内成人在线| 久久免费视频网站| 麻豆亚洲精品| 亚洲国产精品一区在线观看不卡| 久久精品国产一区二区电影 | 亚洲第一搞黄网站| 久久视频在线视频| 鲁鲁狠狠狠7777一区二区| 精品成人国产| 免费av成人在线| 亚洲第一中文字幕在线观看| 亚洲黄色免费网站| 欧美高清视频一区| 亚洲精品综合| 亚洲一区观看| 国产毛片精品国产一区二区三区| 中文一区二区| 久久国产精品久久国产精品 | 男人的天堂亚洲在线| 欧美mv日韩mv国产网站| 亚洲七七久久综合桃花剧情介绍| 美女国产一区| 一区二区欧美激情| 久久电影一区| 亚洲激情偷拍| 国产精品日韩欧美一区二区三区 | 欧美自拍偷拍| 国产精品久久久久aaaa| 欧美在线免费播放| 一区二区黄色| 国产欧美精品日韩精品| 欧美先锋影音| 欧美视频精品一区| 欧美午夜片在线观看| 欧美精品色网| 欧美精品在线免费| 欧美99在线视频观看| 久久综合色婷婷| 久久久噜噜噜久久中文字免| 欧美一区二区精品| 欧美亚洲在线| 老司机久久99久久精品播放免费| 国产美女精品人人做人人爽| 欧美寡妇偷汉性猛交| 久久综合国产精品| 老司机一区二区| 免费视频亚洲| 欧美激情视频在线播放| 欧美乱在线观看| 欧美日产一区二区三区在线观看 | 久久综合99re88久久爱| 久久琪琪电影院| 免费日韩视频| 欧美激情视频网站| 欧美四级电影网站| 国产精品人人做人人爽人人添| 国产精品爽爽ⅴa在线观看| 国产精品一区视频网站| 国产欧美日韩在线| 伊人久久综合| 亚洲区免费影片| 亚洲少妇诱惑| 久久国产精品99国产| 久久亚洲综合色| 亚洲国产第一| 亚洲一卡二卡三卡四卡五卡| 亚洲欧美在线免费| 久久久久久久久综合| 欧美成人xxx| 国产精品久久久免费| 国内精品久久久久久 | 亚洲激情六月丁香| 一区二区三区|亚洲午夜| 亚洲欧洲av一区二区| 久久综合九色综合欧美狠狠| 亚洲高清激情| 亚洲一区免费观看| 老巨人导航500精品| 欧美视频一二三区| 激情久久中文字幕| 一本色道久久综合亚洲精品按摩| 性欧美超级视频| 欧美肥婆在线| 99国产麻豆精品| 久久国产主播精品| 欧美日韩成人综合在线一区二区| 国产日韩一区在线| 日韩网站在线看片你懂的| 午夜视频久久久| 亚洲黄色影院| 久久精品91久久久久久再现| 欧美精品激情在线观看| 国产亚洲一区二区精品| 一本色道久久精品| 免费久久99精品国产自在现线| 99在线精品观看| 蜜臀99久久精品久久久久久软件| 国产精品视频观看| 日韩午夜高潮| 欧美怡红院视频一区二区三区| 99国产精品久久久久久久久久| 136国产福利精品导航| 亚洲系列中文字幕| 欧美成人免费在线视频| 销魂美女一区二区三区视频在线| 欧美日韩国产成人在线91| 激情综合网址| 午夜亚洲性色福利视频| 亚洲精品日韩在线| 久久久精品国产免费观看同学| 国产精品久久久久久久久久尿| 亚洲精品一区在线| 免费欧美电影| 久久国产精品高清| 国产乱码精品一区二区三区不卡| 亚洲激情第一页| 欧美激情亚洲自拍| 久久久久久一区二区三区| 国产午夜精品理论片a级大结局 | 欧美性淫爽ww久久久久无| 亚洲欧洲一区二区三区在线观看| 久久久综合精品| 欧美一区二区免费视频| 国产精品久久久久久一区二区三区 | 亚洲视频在线观看| 亚洲免费观看高清在线观看| 欧美激情综合五月色丁香| 亚洲韩日在线| 亚洲国产精品激情在线观看| 麻豆精品精华液| 亚洲精品久久久久久久久久久久久| 美女爽到呻吟久久久久| 久久一本综合频道| 亚洲狠狠婷婷| 亚洲欧洲日韩综合二区| 欧美日韩不卡视频| 一区二区三区偷拍| 亚洲激情视频网| 欧美成人午夜| 亚洲激精日韩激精欧美精品| 欧美在线高清视频| 久久经典综合| 老牛影视一区二区三区|