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

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>
            韩国v欧美v日本v亚洲v| 国产亚洲欧美日韩一区二区| 亚洲福利电影| 欧美高清在线播放| 美日韩精品免费| 一本色道久久88亚洲综合88 | 国产精品视频免费| 欧美中日韩免费视频| 欧美一区二区视频在线| 国内精品伊人久久久久av影院 | 亚洲国产一二三| 亚洲黄色小视频| 欧美日韩一区二区国产| 99视频精品| 国产日韩欧美麻豆| 欧美成人精精品一区二区频| 欧美精品入口| 久久国产精品久久久| 久久嫩草精品久久久久| 中文精品视频| 欧美在线视屏| 一区二区av在线| 欧美亚洲一级| 夜夜爽夜夜爽精品视频| 亚洲欧美国产毛片在线| 伊人久久久大香线蕉综合直播| 欧美激情偷拍| 国产农村妇女毛片精品久久麻豆 | 欧美一区1区三区3区公司| 国内精品久久久| 亚洲理伦电影| 好看的日韩av电影| 99精品视频免费在线观看| 国产日韩欧美夫妻视频在线观看| 欧美成人国产| 国产区欧美区日韩区| 亚洲黄页视频免费观看| 国产一区二区三区av电影| 日韩视频精品在线| 影音先锋亚洲电影| 亚洲永久免费观看| av成人国产| 美女主播一区| 久久久精品国产免费观看同学 | 亚洲性图久久| 一区二区av在线| 老司机午夜免费精品视频| 欧美与黑人午夜性猛交久久久| 欧美精品videossex性护士| 老**午夜毛片一区二区三区| 国产精品丝袜久久久久久app| 亚洲国产精品va在线观看黑人| 国产一区二区精品在线观看| 亚洲私人影院在线观看| 一区二区激情视频| 欧美黄色一区二区| 欧美成人在线免费观看| 狠狠入ady亚洲精品经典电影| 亚洲视频免费在线| 亚洲视频狠狠| 欧美日韩一区精品| 亚洲精品乱码久久久久久蜜桃91| 亚洲国产精品毛片| 老司机午夜精品视频在线观看| 久久青草欧美一区二区三区| 国产欧美一区二区精品仙草咪| 这里是久久伊人| 亚洲摸下面视频| 国产精品久久久一区二区三区| 亚洲精品综合精品自拍| 一本色道精品久久一区二区三区| 欧美成人精品在线视频| 亚洲国产精品久久久久秋霞影院| 一区在线播放视频| 免费欧美在线视频| 亚洲美女精品成人在线视频| 亚洲小说欧美另类婷婷| 国产精品一区二区久久| 欧美专区18| 欧美大片免费观看| 日韩一区二区精品| 国产精品久久久久久久9999| 亚洲一二三区精品| 久久午夜激情| 亚洲日本在线视频观看| 欧美日韩国产综合视频在线观看| 夜夜嗨av一区二区三区中文字幕| 亚洲欧美日韩精品久久亚洲区| 国产乱理伦片在线观看夜一区| 欧美伊人久久久久久午夜久久久久 | 伊人久久大香线蕉av超碰演员| 另类专区欧美制服同性| 亚洲激情国产| 午夜国产精品视频免费体验区| 国产亚洲欧美激情| 欧美**人妖| 亚洲午夜精品一区二区| 久久一区二区三区国产精品| 日韩视频一区二区在线观看 | 欧美aaaaaaaa牛牛影院| 一区二区三区国产精华| 米奇777超碰欧美日韩亚洲| 99re66热这里只有精品4| 国产精品国产福利国产秒拍| 久久久精彩视频| 日韩视频精品在线| 欧美 日韩 国产精品免费观看| 一区二区三区视频观看| 国内精品国产成人| 欧美亚一区二区| 免费观看亚洲视频大全| 亚洲欧美久久久久一区二区三区| 欧美激情精品| 久久高清免费观看| 亚洲婷婷综合色高清在线| 伊人久久久大香线蕉综合直播 | 欧美一区二区三区啪啪| 亚洲精品资源| 亚洲高清成人| 老鸭窝毛片一区二区三区| 亚洲永久免费视频| 亚洲精品视频在线| 尤物视频一区二区| 国产日韩三区| 国产精品视频最多的网站| 欧美精品二区| 免费不卡中文字幕视频| 久久av一区二区三区漫画| 一区二区三区四区国产| 亚洲精品1区2区| 欧美国产日本在线| 久久综合网络一区二区| 午夜在线视频一区二区区别| 一区二区三区国产盗摄| 亚洲精品色图| 亚洲日本aⅴ片在线观看香蕉| 一色屋精品视频在线看| 国产一区二区三区久久悠悠色av| 国产精品男人爽免费视频1| 国产精品xxx在线观看www| 欧美日韩国内| 欧美日韩国产一中文字不卡| 欧美精品1区2区| 欧美国产日韩一区二区三区| 媚黑女一区二区| 牛人盗摄一区二区三区视频| 蜜臀a∨国产成人精品| 久久午夜电影| 免费久久99精品国产| 免费日韩精品中文字幕视频在线| 蜜臀91精品一区二区三区| 蜜桃av一区二区三区| 欧美/亚洲一区| 欧美国产日本| 欧美日韩视频免费播放| 欧美午夜精品一区| 国产精品亚洲成人| 国产午夜精品久久久久久免费视| 韩国三级电影久久久久久| 伊人婷婷欧美激情| 亚洲日本一区二区三区| 一本色道久久综合狠狠躁篇怎么玩 | 欧美精品久久久久久久| 欧美日韩一区在线观看| 国产精品欧美一区二区三区奶水| 国产精品毛片一区二区三区| 国产偷久久久精品专区| 亚洲大片在线| 在线亚洲欧美| 久久久久久有精品国产| 欧美激情综合| 中文av字幕一区| 久久精视频免费在线久久完整在线看| 久久久久久高潮国产精品视| 欧美激情在线| 国产精品一级久久久| 亚洲国产精品ⅴa在线观看| 一本大道久久a久久精二百| 欧美在线免费视频| 亚洲电影欧美电影有声小说| 一区二区三区日韩| 久久亚洲国产精品日日av夜夜| 欧美日韩国产精品| 红桃视频亚洲| 亚洲欧美精品一区| 欧美大胆a视频| 亚洲欧美韩国| 欧美精品一区在线| 精品999在线观看| 亚洲专区一二三| 亚洲国产精品999| 久久成人18免费观看| 欧美日韩中文字幕精品| 亚洲成色777777在线观看影院| 亚洲男同1069视频| 亚洲三级网站| 美女诱惑一区| 精东粉嫩av免费一区二区三区| 亚洲午夜视频在线| 亚洲国产日韩欧美在线图片|