poj3322 Bloxorz I
Problems
Logout
-11:24:01
Overview
Problem
Status
Rank
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
O - Bloxorz I
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Status
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
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
bfs, , , , , , , , , bfs
#include <iostream>
#include <stdio.h>
#include<string.h>
#include <queue>
using namespace std ;
int n,m,map[605][605],endx,endy,visit[600][600][3];
struct boxtree{
int step,x[2],y[2],state;
};
int fmin(int a,int b)
{
if(a<b)
return a;
else
return b;
}
boxtree p,temp,start;
int dir[3][4][5]={
{
0,-2,0,-1,1,
1,0,2,0,2,
0,1,0,2,1,
-2,0,-1,0,2
},
{
0,-1,-3,-3,0,
1,0,1,1,1,
0,2,-3,-3,0,
-1,0,-1,1,1
},
{
0,-1,1,-1,2,
2,0,-3,-3,0,
0,1,1,1,2,
-1,0,-3,-3,0,
}
};
void init()
{
char str[200];
int i,j;
char c;
start.x[0]=start.x[1]=start.y[0]=start.y[1]=-1;
gets(str);//
for( i=0;i<n;i++)
{
for( j=0;j<m;j++)
{
c=getchar();
if(c=='#')
{
map[i][j]=0;//
}
else if(c=='.')
{
map[i][j]=2;//
}
else if(c=='E')//
{
map[i][j]=1;
}
else if(c=='O')
{
endx=i;
endy=j;
map[i][j]=2;//
}
else if( c=='X')
{
map[i][j]=2;
if(start.x[0]==-1)
{
start.x[0]=i;
start.y[0]=j;
start.state=0; //
}
else
{
start.x[1]=i;
start.y[1]=j;
start.state=1;
if((start.x[0]==start.x[1])&&(start.y[0]!=start.y[1]))
{
start.state=1;//
start.y[0]=fmin(start.y[0],start.y[1]);//
}
else if((start.x[0]!=start.x[1])&&(start.y[0]==start.y[1]))
{
start.state=2;//
start.x[0]=fmin(start.x[0],start.x[1]);//
}
}
}
}
gets(str);
}
//gets(str);
// printf("%d%d end
",endx,endy);
}
bool changestate(int i)
{
p.x[0]=temp.x[0]+dir[temp.state][i][0];//
p.y[0]=temp.y[0]+dir[temp.state][i][1];
p.x[1]=temp.x[0]+dir[temp.state][i][2];
p.y[1]=temp.y[0]+dir[temp.state][i][3];
p.state=dir[temp.state][i][4];
if(p.state==0)//
{
if((p.x[0]>=0)&&(p.x[0]<n)&&(p.y[0]>=0&&p.y[0]<m)&&(map[p.x[0]][p.y[0]]==2)&&(visit[p.x[0]][p.y[0]][0]==0))
{
visit[p.x[0]][p.y[0]][0]=1;//
return true;
}
else
{
return false ;
}
}
else if(p.state==1)//
{
if((p.x[0]>=0)&&(p.x[0]<n)&&(p.y[0]>=0&&p.y[0]<m-1)&&(map[p.x[0]][p.y[0]]!=0)&&(map[p.x[1]][p.y[1]]!=0)&&(visit[p.x[0]][p.y[0]][1]==0))
{
visit[p.x[0]][p.y[0]][1]=1;//
return true;
}
else
{
return false ;
}
}
else if( p.state==2)//
{
if((p.x[0]>=0)&&(p.x[0]<n-1)&&(p.y[0]>=0&&p.y[0]<m)&&(map[p.x[0]][p.y[0]]!=0)&&map[p.x[1]][p.y[1]]!=0&&(visit[p.x[0]][p.y[0]][2]==0))
{
visit[p.x[0]][p.y[0]][2]=1;//
return true;
}
else
{
return false ;
}
}
return false ;
}
int bfs()
{
int i;
queue<boxtree> q;
memset(visit,0,sizeof(visit));
while(!q.empty())//
{
q.pop();
}
start.step=0;
q.push(start);
while(!q.empty())
{
temp=q.front();
q.pop();
for( i=0;i<4;i++)//4
{
if(changestate(i))
{
p.step=temp.step+1;
q.push(p);
// printf("%d %d %d
",p.x[0],p.y[0],p.state);
if((p.x[0]==endx)&&(p.y[0]==endy)&&(p.state==0))
{
printf("%d
",p.step);
return 1;
}
}
}
}
printf("Impossible
");
return -1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
{
init();
bfs();
}
return 0;
}
FAQ | About Virtual Judge | Forum | Discuss | Open Source Project
All Copyright Reserved ©2010-2012 HUST ACM/ICPC TEAM
Anything about the OJ, please ask in the forum, or contact author: Isun
Server Time:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Golang JSON 구조체를 이용한 JSON 데이터 인코딩 방법메서드 단계: 1. 구조체를 먼저 성명한다. 2. 실례화된 구조체를 정의한다. 구조체에 값을 부여한다. 3. json을 사용합니다.Marshal은 구조체 데이터를 JSON 데이터 형식으로 인코딩합니다. 4. 가능: ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.