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

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>
            国产欧美精品| 欧美日韩国语| 亚洲国产成人久久综合一区| 欧美中文字幕视频| 久久精品国产第一区二区三区最新章节| 国产精品日韩在线观看| 久久精品日产第一区二区三区| 欧美在线免费看| 91久久久久| av成人免费| 红桃视频国产一区| 亚洲黄色av一区| 欧美午夜女人视频在线| 久久国产夜色精品鲁鲁99| 久久久7777| 一区二区三区日韩在线观看| 亚洲一二三区在线| 黄色精品一区二区| 99re6热只有精品免费观看| 国产情人节一区| 亚洲欧洲精品天堂一级| 国产九区一区在线| 亚洲黄色在线看| 国产一级揄自揄精品视频| 亚洲二区视频| 国模私拍一区二区三区| 亚洲人成亚洲人成在线观看| 国产欧美日韩精品丝袜高跟鞋| 欧美黑人国产人伦爽爽爽| 国产精品久久久一区二区| 欧美二区在线| 国产一区二区精品在线观看| 日韩视频免费| 亚洲国产精品尤物yw在线观看| 日韩午夜在线电影| 亚洲人成网站999久久久综合| 亚洲欧美成人一区二区三区| 亚洲精品综合在线| 久久乐国产精品| 欧美在线播放一区| 欧美午夜视频网站| 亚洲国产精品一区二区www在线 | 免费在线成人av| 国产精品久久久久久户外露出| 欧美黑人一区二区三区| 国户精品久久久久久久久久久不卡| 亚洲精品欧美| 亚洲国产国产亚洲一二三| 午夜精品视频一区| 午夜视频在线观看一区二区三区 | 亚洲欧美国产不卡| 亚洲在线一区二区三区| 欧美日韩网站| 亚洲人成在线播放| 日韩视频免费观看高清在线视频| 久久久www成人免费毛片麻豆| 久久精品国产成人| 国产亚洲成人一区| 香蕉精品999视频一区二区| 欧美亚洲一级| 国产午夜精品全部视频在线播放| 亚洲午夜羞羞片| 欧美在线观看视频一区二区三区| 欧美性视频网站| 亚洲欧美综合国产精品一区| 欧美与黑人午夜性猛交久久久| 国产欧美日韩伦理| 欧美在线free| 免费在线看成人av| 亚洲三级影片| 欧美三级第一页| 亚洲永久免费| 久久亚洲欧美国产精品乐播| 尹人成人综合网| 欧美成人午夜剧场免费观看| 亚洲欧洲日本在线| 亚洲欧美日韩一区二区| 国产欧美日本一区视频| 久久岛国电影| 亚洲国产精品成人一区二区| 一区二区三区精品| 国产农村妇女精品一二区| 久久国产精品久久国产精品| 你懂的亚洲视频| 亚洲视屏在线播放| 国产日韩欧美一二三区| 久久免费视频一区| 亚洲美女精品成人在线视频| 亚洲欧美电影院| 伊人久久大香线蕉综合热线| 欧美精品在线观看播放| 亚洲一区二区三区在线| 欧美大片在线观看一区| 亚洲视频视频在线| 在线播放国产一区中文字幕剧情欧美| 农夫在线精品视频免费观看| 一片黄亚洲嫩模| 鲁大师影院一区二区三区| av成人手机在线| 极品裸体白嫩激情啪啪国产精品| 欧美激情综合在线| 久久国产精品99国产精| 99re66热这里只有精品4| 免费成人毛片| 性欧美videos另类喷潮| 亚洲欧洲综合另类| 国产色综合久久| 欧美日韩国产一区二区三区| 欧美一区二区福利在线| 日韩视频免费| 亚洲国产精品精华液2区45| 欧美在线看片| 亚洲视频碰碰| 亚洲毛片网站| 亚洲第一视频| 狠狠干综合网| 国产一区二区黄| 欧美午夜一区二区福利视频| 免费亚洲视频| 久久久久久国产精品一区| 亚洲摸下面视频| 一区二区激情| 99视频一区二区三区| 亚洲国产导航| 欧美激情网站在线观看| 米奇777在线欧美播放| 久久精品99国产精品日本| 亚洲一区不卡| 亚洲免费视频在线观看| 99视频一区| aa成人免费视频| 99视频一区二区| 一本一本大道香蕉久在线精品| 亚洲国产精品激情在线观看| 伊人狠狠色j香婷婷综合| 黑丝一区二区| 韩国v欧美v日本v亚洲v | 欧美成人有码| 欧美大片网址| 欧美精品在线观看播放| 欧美啪啪成人vr| 欧美日韩八区| 国产精品啊v在线| 欧美视频在线观看一区| 国产精品va| 国产乱码精品1区2区3区| 国产精品中文在线| 国产午夜精品视频| 黑人操亚洲美女惩罚| 亚洲福利视频免费观看| 亚洲精品激情| 亚洲婷婷在线| 欧美一区二区日韩一区二区| 欧美在线亚洲在线| 噜噜噜躁狠狠躁狠狠精品视频 | 久久av一区二区| 毛片精品免费在线观看| 欧美激情一区二区久久久| 亚洲国产精品第一区二区| 亚洲精品在线看| 亚洲欧美成人| 老司机午夜精品视频| 欧美精品色综合| 国产精品午夜视频| 亚洲福利免费| 亚洲综合激情| 蜜桃av综合| 99热在线精品观看| 久久精品国产亚洲5555| 欧美精品色一区二区三区| 国产精品欧美一区二区三区奶水| 国产综合av| 99视频精品全国免费| 久久久久国产免费免费| 亚洲精品1区| 性18欧美另类| 欧美日韩日本视频| 狠色狠色综合久久| 亚洲综合社区| 亚洲国产欧美一区| 欧美亚洲视频| 欧美日韩在线三区| 亚洲国产精品久久久久秋霞影院 | 亚洲成人在线| 午夜在线观看免费一区| 亚洲福利视频三区| 香蕉久久国产| 国产精品国产三级国产普通话99| 怡红院精品视频在线观看极品| 亚洲在线成人| 亚洲毛片在线观看| 免费不卡中文字幕视频| 国产真实久久| 欧美亚洲网站| 一本久道久久综合中文字幕| 蜜臀久久99精品久久久画质超高清 | 久久久久久久国产| 国产午夜精品久久久久久久| 中文av一区特黄| 91久久久久久久久|