The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3322 Bloxorz I(BFS, 改编自同名游戏,很不错的一题)

Bloxorz I

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


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 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.


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
0 0

Sample Output




//This is the sorce code for POJ 3322
//created by abilitytao
//special thanks to Rainer
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}},

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;    

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)

else if(temp[j]=='X'&&flag==1)

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




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;}
return s;

int main()
int r,c;
int i,j;
int endx,endy;
int newx,newy;
int newstate;
int front=1;
int rear=1;





return 0;

posted on 2009-08-16 22:25 abilitytao 阅读(1710) 评论(4)  编辑 收藏 引用


# re: POJ 3322 Bloxorz I(BFS, 改编自同名游戏,很不错的一题) 2009-08-16 23:30 expter


LZ大几啊。。。  回复  更多评论   

# re: POJ 3322 Bloxorz I(BFS, 改编自同名游戏,很不错的一题) 2009-08-16 23:49 abilitytao

大二 学长多多指教啊  回复  更多评论   

# re: POJ 3322 Bloxorz I(BFS, 改编自同名游戏,很不错的一题) 2009-08-19 14:40 个性艺术签名

上岛咖啡书店  回复  更多评论   

# re: POJ 3322 Bloxorz I(BFS, 改编自同名游戏,很不错的一题) 2009-08-31 11:22 路过

呵呵 发现我是第1000个阅读者呢 飘过哈 ~  回复  更多评论   

【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理