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

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

POJ 3322 Bloxorz I(BFS, 改編自同名游戲,很不錯的一題)

Bloxorz I

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 2624 Accepted: 882

Description

Little Tom loves playing games. One day he downloads a little computer game called 'Bloxorz' which makes him excited. It's a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.


The box stands on a single cell

 


The box lies on two neighbouring cells, horizontally

 


The box lies on two neighbouring cells, vertically

 

After Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.

Input

Input contains multiple test cases. Each test case is one single stage of the game. It starts with two integers R and C(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains R lines and C characters for each line, with 'O' (Oh) for target cell, 'X' for initial position of the box, '.' for a rigid cell, '#' for a empty cell and 'E' for a easily broken cell. A test cases starts with two zeros ends the input.

It guarantees that

  • There's only one 'O' in a plane.
  • There's either one 'X' or neighbouring two 'X's in a plane.
  • The first(and last) row(and column) must be '#'(empty cell).
  • Cells covered by 'O' and 'X' are all rigid cells.

Output

For each test cases output one line with the minimum number of moves or "Impossible" (without quote) when there's no way to achieve the target cell.  

Sample Input

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

Sample Output

10

Source




此題是標準的BFS,但是要注意優化,寫的不好代碼很容易超過5000B.
1.首先是狀態壓縮,積木可以立起來,也可以朝向上下左右躺下,其實向左躺和向右躺下實際上是同一種狀態,向上躺和向下躺亦然,所以本題可以壓縮成3個狀態,這里用1表示直立,2表示橫躺,3表示豎躺,可以節省大量空間花費;
2.用隊列進行廣搜的時候最好不要使用STL的queue容器,由于queue的初始值有限,搜索的時候需要大量移動內存中的數據,效率比較低,不妨手工直接模擬一個隊列。
3.在搜索的時候,由于狀態空間比較大,如果一一列出,代碼過于冗長,比較好的方法是用一個三維矩陣來存儲狀態之間的關系,這樣搜索的過程可以只用一個for循環來實現,代碼十分精簡。
4.最好進行初始化,讀入數據的時候將其轉化成整數,這樣操作起來比較方便。

下面是我的代碼:
//This is the sorce code for POJ 3322
//created by abilitytao
//Time:2009年8月16日22:33:08
//special thanks to Rainer
#include<iostream>
using namespace std;
#define MAX 502
#define LINEMAX 9000000

struct node
{
    
int x,y;
    
int step;
    
int state;//1代表直立,2代表水平放,3代表垂直放
}
;

bool visit[MAX][MAX][4];
int graph[MAX][MAX];//0->empty cell,1->weak cell,2->rigid cell
node l[LINEMAX];

int dir[3][4][3]={{{0,-1,2},{-2,0,1},{0,2,2},{1,0,1}},
                
{{0,-1,0},{-1,0,-1},{0,1,0},{2,0,-1}},
                
{{0,-2,-2},{-1,0,0},{0,1,-2},{1,0,0}}}
;




inline 
bool check(int x,int y,int state)
{
    
if(graph[x][y]==0return false;
    
if(state==1&&graph[x][y]==1return false;
    
else if(state==2&&graph[x+1][y]==0)    return false;
    
else if(state==3&&graph[x][y-1]==0)    return false;
    
return true;
}




inline node inputgraph(
int r,int c,int &endx,int &endy)
{

    
int i,j;
    
int len;
    
char temp[MAX];
    
int x1=0,y1=0;
    
int x2=0,y2=0;
    
int flag=0;
    node s;    
    memset(graph,
0,sizeof(graph));//Graph矩陣清0
    memset(visit,0,sizeof(visit));//visit矩陣清0
    for(i=1;i<=r;i++)
    
{

        scanf(
"%s",temp);
        len
=strlen(temp);
        
for(j=0;j<len;j++)
        
{
            
if(temp[j]=='#') graph[j+1][i]=0;
            
else if(temp[j]=='E') graph[j+1][i]=1;
            
else if(temp[j]=='.') graph[j+1][i]=2;
            
else if(temp[j]=='X'&&flag==0)
            
{
                graph[j
+1][i]=2;
                x1
=j+1;y1=i;
                flag
=1;
            }

            
else if(temp[j]=='X'&&flag==1)
            
{
                graph[j
+1][i]=2;
                x2
=j+1;y2=i;
            }

            
else if(temp[j]=='O')
            
{

                graph[j
+1][i]=2;
                endx
=j+1;
                endy
=i;
            }

        }

    }

    
if(x1!=0&&x2!=0&&y1!=0&&y2!=0)
    
{
        
if(y1<y2) {s.x=x1;s.y=y2;s.state=3;}
        
else if(x1<x2) {s.x=x1;s.y=y1;s.state=2;}
    }

    
else {s.x=x1;s.y=y1;s.state=1;}
    s.step
=0;
    
return s;
}



int main()
{
    
    
int r,c;
    
int i,j;
    
int endx,endy;
    
int newx,newy;
    
int newstate;
    
while(scanf("%d%d",&r,&c))
    
{
        
        
if(r==0&&c==0)
            
break;
        
int front=1;
        
int rear=1;
        l[front]
=inputgraph(r,c,endx,endy);
        visit[l[front].x][l[front].y][l[front].state]
=1;
        
while(front<=rear)
        
{
            
if(l[front].x==endx&&l[front].y==endy&&l[front].state==1)
            
{
                printf(
"%d\n",l[front].step);
                
break;
            }


            
for(j=0;j<4;j++)
            
{
                newx
=l[front].x+dir[l[front].state-1][j][0];
                newy
=l[front].y+dir[l[front].state-1][j][1];
                newstate
=l[front].state+dir[l[front].state-1][j][2];
                
if(!visit[newx][newy][newstate]&&check(newx,newy,newstate))
                
{
                    
                    rear
=rear++;
                    l[rear].x
=newx;
                    l[rear].y
=newy;
                    l[rear].state
=newstate;
                    visit[newx][newy][newstate]
=1;
                    l[rear].step
=l[front].step+1;
                }

            }

        
        front
++;
        }

        
if(front>rear)
            printf(
"Impossible\n");
    }

    
return 0;
}



posted on 2009-08-16 22:25 abilitytao 閱讀(1868) 評論(4)  編輯 收藏 引用

評論

# re: POJ 3322 Bloxorz I(BFS, 改編自同名游戲,很不錯的一題) 2009-08-16 23:30 expter

好多acmer。。。

LZ大幾啊。。。  回復  更多評論   

# re: POJ 3322 Bloxorz I(BFS, 改編自同名游戲,很不錯的一題) 2009-08-16 23:49 abilitytao

@expter
大二 學長多多指教啊  回復  更多評論   

# re: POJ 3322 Bloxorz I(BFS, 改編自同名游戲,很不錯的一題) 2009-08-19 14:40 個性藝術簽名

上島咖啡書店  回復  更多評論   

# re: POJ 3322 Bloxorz I(BFS, 改編自同名游戲,很不錯的一題) 2009-08-31 11:22 路過

呵呵 發現我是第1000個閱讀者呢 飄過哈 ~  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            一区二区三区国产精华| 国产午夜精品久久久| 国产美女诱惑一区二区| 亚洲清纯自拍| 亚洲黄色影院| 久色婷婷小香蕉久久| 亚洲国产精品精华液网站| 欧美黑人国产人伦爽爽爽| 麻豆精品一区二区av白丝在线| 狠狠色狠色综合曰曰| 欧美国产视频一区二区| 欧美激情精品久久久久久免费印度| 日韩视频免费观看| 亚洲视频网站在线观看| 国产伦一区二区三区色一情| 久久躁狠狠躁夜夜爽| 欧美国产精品人人做人人爱| 在线亚洲美日韩| 亚洲欧美一区二区三区久久| 在线观看亚洲专区| 亚洲精品自在久久| 国产一区二区三区av电影| 免费观看亚洲视频大全| 欧美高清hd18日本| 午夜宅男久久久| 久久久精品国产99久久精品芒果| 亚洲激情视频网站| 最新高清无码专区| 亚洲女女女同性video| 激情文学一区| 一本一本久久a久久精品综合麻豆 一本一本久久a久久精品牛牛影视 | 久久综合网hezyo| 亚洲精选91| 欧美一级视频免费在线观看| 亚洲激情黄色| 亚洲淫性视频| 亚洲毛片播放| 久久精品道一区二区三区| 这里只有精品视频| 欧美成人亚洲| 久久精品亚洲| 国产精品久久久久久av福利软件| 免费观看亚洲视频大全| 国产伦精品免费视频| 亚洲欧洲日夜超级视频| 一区二区在线观看av| 亚洲欧美日韩一区二区在线| 一区二区电影免费观看| 快播亚洲色图| 久久网站热最新地址| 国产伦精品一区二区三区照片91 | 亚洲欧美日韩精品在线| 亚洲深夜福利视频| 欧美成人午夜激情| 欧美粗暴jizz性欧美20| 国产日韩亚洲欧美综合| 一区二区91| 亚洲免费伊人电影在线观看av| 欧美激情一级片一区二区| 免费久久99精品国产自| 黄网动漫久久久| 久久国产精品72免费观看| 久久精品电影| 国产视频一区在线| 午夜一区二区三区不卡视频| 亚洲欧美卡通另类91av| 欧美日韩中文| 中国成人在线视频| 亚洲欧美久久久| 国产欧美精品国产国产专区| 小黄鸭精品密入口导航| 欧美一区成人| 国产亚洲毛片| 老司机成人网| 亚洲国产成人在线| 亚洲精品一区二区三区在线观看 | 欧美一区二区在线免费观看| 久久久亚洲影院你懂的| 激情文学一区| 米奇777超碰欧美日韩亚洲| 亚洲激情国产| 亚洲无毛电影| 国产日韩综合| 狂野欧美激情性xxxx| 亚洲国产美女精品久久久久∴| 亚洲美女尤物影院| 欧美亚洲一区在线| 美玉足脚交一区二区三区图片| 亚洲国产精品激情在线观看| 欧美日韩国产不卡在线看| 一级成人国产| 美女脱光内衣内裤视频久久影院| 亚洲精品欧洲| 国产精品婷婷午夜在线观看| 久久精品国产99国产精品| 欧美粗暴jizz性欧美20| 亚洲天堂网在线观看| 国产欧美三级| 欧美精品导航| 香蕉尹人综合在线观看| 亚洲电影av在线| 午夜视黄欧洲亚洲| 亚洲国产成人在线| 国产精品福利在线观看网址| 久久精品女人的天堂av| 亚洲美女av在线播放| 久久综合九色综合欧美狠狠| 一区二区三区日韩欧美| 国外成人在线视频| 欧美日韩成人一区二区| 久久久久国产精品人| 夜夜嗨一区二区三区| 欧美成人综合在线| 久久国产加勒比精品无码| 最新国产精品拍自在线播放| 国产日韩av在线播放| 欧美日韩视频免费播放| 蜜臀va亚洲va欧美va天堂| 欧美一区二区三区四区高清| 亚洲精品中文字幕在线| 美女在线一区二区| 久久激情视频| 亚洲自拍偷拍福利| 99视频国产精品免费观看| 精品二区视频| 国产精品久久久久久影视| 欧美韩日一区二区| 久久久噜噜噜久噜久久| 午夜日韩福利| 亚洲免费人成在线视频观看| 亚洲免费观看在线观看| 男女精品网站| 久久蜜桃资源一区二区老牛 | 亚洲精品久久久久久久久久久久久| 国产精品久久久久久五月尺| 欧美视频一区在线观看| 欧美激情一区二区三区在线视频观看| 久久久999精品视频| 亚洲欧美一区二区三区极速播放 | 美女脱光内衣内裤视频久久影院 | 久久精品夜夜夜夜久久| 欧美在线视频免费| 香蕉av777xxx色综合一区| 亚洲欧美成人| 午夜精品免费在线| 午夜亚洲视频| 久久精品国产综合精品| 欧美中文字幕在线| 久久激情视频久久| 久久天堂成人| 欧美va天堂| 欧美成人午夜影院| 欧美日韩精品一区二区在线播放 | 欧美日韩一区二区三区视频| 欧美日韩www| 国产精品wwwwww| 国产欧美日韩在线| 一区在线播放| 亚洲啪啪91| 亚洲桃花岛网站| 欧美中文在线字幕| 老巨人导航500精品| 亚洲第一毛片| 日韩视频欧美视频| 亚洲欧美国产三级| 久久综合五月| 欧美日韩国产一区| 国产一区二区在线免费观看 | 欧美日韩久久| 国产精品日日摸夜夜摸av| 国产日韩欧美二区| 亚洲国产日韩欧美在线动漫| a4yy欧美一区二区三区| 亚洲主播在线观看| 久久综合色婷婷| 亚洲精品视频免费| 午夜在线电影亚洲一区| 欧美+亚洲+精品+三区| 国产精品第三页| 在线播放豆国产99亚洲| 中文在线资源观看网站视频免费不卡| 校园春色国产精品| 亚洲第一精品夜夜躁人人躁| 亚洲视频一区在线| 久久亚洲国产精品日日av夜夜| 欧美日韩中文字幕在线视频| 国产一区二区av| 中国成人亚色综合网站| 美女国产精品| 亚洲影院一区| 欧美伦理91i| 亚洲第一网站免费视频| 午夜免费日韩视频| 亚洲国产一区二区在线| 久久激情视频久久| 国产精品专区h在线观看| 亚洲免费激情| 男同欧美伦乱| 欧美影院成人| 国产伦精品一区二区三区高清版|