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

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>
            国产精品theporn| 亚洲综合精品自拍| 欧美一区视频在线| 中文一区字幕| 国产欧美精品一区aⅴ影院| 欧美在线一二三区| 久久精品国产欧美激情| 依依成人综合视频| 亚洲大胆人体视频| 亚洲国产精品久久久久秋霞影院 | 亚洲一区精彩视频| 亚洲一区免费视频| 激情欧美日韩一区| 亚洲精品美女在线| 国产午夜精品久久久久久免费视| 久久久精品日韩| 欧美黑人多人双交| 欧美一区亚洲| 欧美精品日韩www.p站| 午夜精品久久99蜜桃的功能介绍| 久久精品亚洲一区二区三区浴池| 亚洲国产视频一区| 亚洲视频中文| 亚洲人成在线免费观看| 亚洲一区二区三区乱码aⅴ蜜桃女 亚洲一区二区三区乱码aⅴ | 亚洲天堂免费观看| 激情五月***国产精品| 最新成人在线| 精品动漫3d一区二区三区| 亚洲精品亚洲人成人网| 禁断一区二区三区在线| 99热在这里有精品免费| 精品白丝av| 亚洲欧美经典视频| 亚洲最新在线| 久久婷婷亚洲| 久久精品免费看| 亚洲欧美日本精品| 99精品视频免费观看视频| 欧美一区二区三区久久精品茉莉花| 亚洲精品中文字幕在线观看| 欧美在线视频免费播放| 亚洲欧美日韩一区二区在线 | 亚洲毛片视频| 亚洲欧洲日本在线| 久久久久综合| 久久久久免费视频| 国产精品日韩专区| 一本久久精品一区二区| 亚洲精品中文字幕有码专区| 久久综合色一综合色88| 久久久久久久综合日本| 国产精品美女久久| 一区二区欧美亚洲| 一区二区三区视频在线观看| 欧美~级网站不卡| 女生裸体视频一区二区三区| 国产精品亚洲综合| 亚洲欧美自拍偷拍| 欧美亚洲午夜视频在线观看| 国产精品劲爆视频| 亚洲少妇最新在线视频| 亚洲欧美日韩电影| 国产精品家教| 午夜精品亚洲| 久久久久久网站| 影音先锋成人资源站| 久久婷婷国产综合精品青草| 欧美91福利在线观看| 亚洲电影在线播放| 欧美成人国产一区二区| 亚洲第一视频| 一区二区动漫| 国产精品久久久久7777婷婷| 亚洲一区二区伦理| 久久久久国产一区二区| 在线观看久久av| 男女精品视频| 日韩视频一区二区三区| 亚洲综合精品| 激情久久综合| 欧美精品少妇一区二区三区| 日韩一二三区视频| 久久精品国产99| 亚洲国产成人av| 欧美性猛交一区二区三区精品| 亚洲一级片在线观看| 久久综合网络一区二区| 亚洲欧洲一区二区三区| 国产精品久久| 久久精品国产欧美亚洲人人爽| 亚洲国产经典视频| 亚洲制服av| 一区二区在线不卡| 欧美精品综合| 久久精品欧美日韩精品| 亚洲人成网站在线观看播放| 亚洲专区一区| 亚洲国内高清视频| 国产精品综合| 欧美freesex交免费视频| 亚洲一级片在线看| 亚洲激情av在线| 久久www免费人成看片高清| 亚洲国产精品123| 国产精品一区=区| 蘑菇福利视频一区播放| 亚洲欧美日本另类| 亚洲伦理在线| 欧美成人免费一级人片100| 亚洲一区二区三区四区五区午夜| 国产资源精品在线观看| 国产精品家教| 欧美日韩xxxxx| 久久亚洲精选| 性欧美超级视频| 99视频精品免费观看| 亚洲国产另类久久精品| 久久久久五月天| 午夜精品一区二区在线观看| 99热精品在线| 亚洲国产精品激情在线观看| 国产日韩视频一区二区三区| 欧美视频一区二区三区| 欧美成人69| 久久久久久网站| 久久精品国产免费| 欧美中文在线免费| 亚洲摸下面视频| 亚洲一区二区三区免费观看| 日韩午夜电影| 亚洲美女av在线播放| 亚洲激情一区| 亚洲精品你懂的| 欧美成人在线影院| 免费的成人av| 欧美91福利在线观看| 女人色偷偷aa久久天堂| 欧美粗暴jizz性欧美20| 欧美激情精品久久久久久| 免费在线亚洲欧美| 男女精品视频| 欧美岛国激情| 亚洲国产精品成人va在线观看| 欧美v国产在线一区二区三区| 久久亚洲综合网| 久久亚洲美女| 欧美国产日本| 亚洲人成网站在线观看播放| 亚洲免费高清视频| 一区二区日本视频| 性色一区二区| 久久精品免视看| 欧美高清视频在线| 欧美日韩精品综合在线| 欧美午夜视频在线观看| 国产精品自拍视频| 在线日韩欧美| 一区二区日韩| 欧美在线视频在线播放完整版免费观看| 亚洲欧美国产77777| 久久精品久久综合| 欧美黑人多人双交| 99在线热播精品免费99热| 亚洲欧美日韩国产一区二区| 久久久精品国产免大香伊 | 午夜亚洲精品| 欧美freesex交免费视频| 欧美日韩精品一区二区| 国产伦精品免费视频| 一区二区自拍| 在线一区视频| 狂野欧美激情性xxxx欧美| 亚洲日本视频| 欧美一级免费视频| 欧美大片一区二区| 国产亚洲福利| 一本久道综合久久精品| 久久国产福利| 亚洲精品免费网站| 久久久久.com| 国产精品av久久久久久麻豆网| 国内精品久久久久久久97牛牛| 亚洲精品乱码久久久久久| 久久福利电影| 亚洲精品美女在线观看播放| 久久国产精品毛片| 国产精品videosex极品| 亚洲国产女人aaa毛片在线| 午夜精品久久久久99热蜜桃导演| 欧美激情一区二区久久久| 亚洲——在线| 欧美视频第二页| 亚洲国产精品一区二区三区| 欧美一区二区视频在线观看2020| 亚洲欧洲在线一区| 久久久噜噜噜久久久| 国产伦精品一区二区三区在线观看 | 国产亚洲成年网址在线观看| 亚洲综合不卡|