码农题,我服了.
首先这显然是一道搜索题,我们先确定搜索的状态:当前方块的x坐标(有两个则取小的,后同),y坐标以及摆的方式dir
不妨钦定1表示立着,2表示横向躺着,3表示纵向躺着.
又由于要求最少步数,我们采用bfs.
总过程分为三部分:
1. 读入
2. 处理出起点和重点的状态
3. 从起点开始bfs,直到到达终点的状态(不是到达重点就行了)
为了避免bfs的过多判断,不妨预处理出移动后x,y变化和dir变化数组,bfs时循环上下左右四种方法即可
为了避免多次走到同一个状态,对走到的状态进行步数记录
有点英文注释
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
else c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
/**********/
#define MAXN 511
char a[MAXN][MAXN];
struct rac
{
ll x,y,dir;
/*
* dir=1:stand
* dir=2:lie in row
* dir=3:lie in col
*/
rac(ll _x=0,ll _y=0,ll _dir=0)
{
x=_x,y=_y,dir=_dir;
}
}start,end;
ll n,m;
ll mx[5]={0,-1,1,0,0},my[5]={0,0,0,-1,1};//up,down,left,right
bool in(ll x,ll y)
{
return x>0&&x<=n&&y>0&&y<=m;
}
void make_st()
{
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
{
if(a[i][j]=='X')
{
for(ll op=1;op<=4;++op)
{
ll x=i+mx[op],y=j+my[op];
if(in(x,y)&&a[x][y]=='X')
{
start=rac(min(i,x),min(j,y),op>2?2:3);
a[i][j]=a[x][y]='.';
}
}
if(a[i][j]=='X')
{
start=rac(i,j,1);
}
}
else if(a[i][j]=='O')
{
end=rac(i,j,1);
a[i][j]='.';
}
}
}
std::queue<rac>q;
ll f[MAXN][MAXN][5];
ll dx[5][5]={{0},{0,-2,1,0,0},{0,-1,1,0,0},{0,-1,2,0,0}};//change of x(dir=i,op=j)
ll dy[5][5]={{0},{0,0,0,-2,1},{0,0,0,-1,2},{0,0,0,-1,1}};//change of y(dir=i,op=j)
ll ddir[5][5]={{0},{0,3,3,2,2},{0,2,2,1,1},{0,1,1,3,3}};//change of dir(dir=i,op=j)
bool check(ll x,ll y,ll dir)
{
if(!in(x,y))return 0;
if(a[x][y]=='#')return 0;
if(dir==1&&a[x][y]=='E')return 0;
if(dir==2&&a[x][y+1]=='#')return 0;
if(dir==3&&a[x+1][y]=='#')return 0;
return 1;
}
ll bfs()
{
while(!q.empty())q.pop();
f[start.x][start.y][start.dir]=1;
q.push(start);
while(!q.empty())
{
rac now=q.front();q.pop();
//printf("%lld %lld %lld\n",now.x,now.y,now.dir);
for(ll op=1;op<=4;++op)
{
ll x=now.x+dx[now.dir][op],y=now.y+dy[now.dir][op],dir=ddir[now.dir][op];
if(!check(x,y,dir)||f[x][y][dir])continue;
f[x][y][dir]=f[now.x][now.y][now.dir]+1;
q.push(rac(x,y,dir));
if(x==end.x&&y==end.y&&dir==end.dir)return f[x][y][dir]-1;
}
}
return -1;
}
int main()
{
while(1)
{
n=read(),m=read();
if(n==0&&m==0)break;
memset(f,0,sizeof f);
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
{
char c = getchar();
while (c != '#' && c != '.' && c != 'E' && c != 'X' && c != 'O')c = getchar();
a[i][j] = c;
}
make_st();
//printf("start=%lld %lld %lld\n",start.x,start.y,start.dir);
//printf("end=%lld %lld %lld\n",end.x,end.y,end.dir);
ll ans=bfs();
if(ans!=-1)printf("%lld\n",ans);
else puts("Impossible");
}
return 0;
}