50pts蒟蒻求调,悬关
  • 板块P10485 Bloxorz I
  • 楼主terytry
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/7 10:07
  • 上次更新2024/10/7 11:42:27
查看原帖
50pts蒟蒻求调,悬关
1121233
terytry楼主2024/10/7 10:07

我也不知道为什么不用特意考虑E

#include<bits/stdc++.h>
using namespace std;
/*1.lie是0代表这个长方体是站着的
2、lie是1代表这个长方体是躺着的 横着 且x,y表示左侧的坐标
3.lie是2代表躺着的 竖着 且x,y代表上侧的坐标*/
struct rec
{
	int x,y,lie;
};
rec st,ed;
queue<rec> q;
char cur[550][550];
int n,m,d[550][550][3];
const int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};
const int next_x[3][4]= {{1,-2,0,0},{1,-1,0,0},{2,-1,0,0}}; //next_x[i][j]表示lie=i时朝着j方向翻滚后的点的信息
const int next_y[3][4]= {{0,0,1,-2},{0,0,2,-1},{0,0,1,-1}};
const int next_lie[3][4]= {{2,2,1,1},{1,1,0,0,},{0,0,2,2}};
bool ck(int x,int y)
{
	if(x>n||x<1||y>m||y<1) return 0;
	return 1;
}
void op()
{
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(cur[i][j]=='O')
				{
					ed.x=i,ed.y=j,ed.lie=0;
					cur[i][j]='.';
				}
			else if(cur[i][j]=='X')
				{
					for(int k=0; k<4; k++)
						{
							int nx=i+dx[k],ny=j+dy[i];
							if(cur[nx][ny]=='X'&&ck(nx,ny))
								{
									st.x=min(i,nx);
									st.y=min(j,ny);
									if(k<2)
										{
											st.lie=2;
										}
									else st.lie=1;
									cur[i][j]=cur[nx][ny]='.';
									break;
								}
						}
					if(cur[i][j]=='X') st.x=i,st.y=j,st.lie=0;
				}
}
bool hf(rec next)
{
	if(!ck(next.x,next.y)) return 0;
	if(cur[next.x][next.y]=='#') return 0;
	if(next.lie==0&&cur[next.x][next.y]!='.') return 0;
	if(next.lie==1&&cur[next.x][next.y+1]=='#') return 0;
	if(next.lie==2&&cur[next.x+1][next.y]=='#') return 0;
//	if(next.lie==1&&cur[next.x][next.y]=='E'&&cur[next.x][next.y+1]=='E') return 0;
//	if(next.lie==2&&cur[next.x][next.y]=='E'&&cur[next.x+1][next.y]=='E') return 0;
	return 1;
}
int bfs()
{
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			for(int k=0; k<3; k++)
				d[i][j][k]=-1;
	while(q.size()) q.pop();
	d[st.x][st.y][0]=0;
	q.push(st);
	while(!q.empty())
		{
			rec now=q.front();
			q.pop();

			for(int i=0; i<4; i++)
				{
					rec next;
					next.x=next_x[now.lie][i]+now.x;
					next.y=next_y[now.lie][i]+now.y;
					next.lie=next_lie[now.lie][i];
					if(!hf(next)) continue;
					if(d[next.x][next.y][next.lie]==-1)
						{
							d[next.x][next.y][next.lie]=d[now.x][now.y][now.lie]+1;
							q.push(next);
							if(next.x==ed.x&&next.y==ed.y&&next.lie==ed.lie)
								return d[next.x][next.y][next.lie];
						}
				}
		}
	return -1;
}

int main()
{
	while(cin>>n>>m&&n)
		{
			for(int i=1; i<=n; i++) cin>>cur[i]+1;
			op();
			int ans=bfs();
			if(ans==-1) puts("Impossible");
			else cout<<ans<<"\n";
		}
	return 0;
}
2024/10/7 10:07
加载中...