样例没过全WA,玄关求条
查看原帖
样例没过全WA,玄关求条
1105009
Yangxixuan楼主2025/7/25 11:12
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
const int next_x[3][4]={{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};
const int next_y[3][4]={{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};
const int next_lie[3][4]={{1,1,2,2},{0,0,1,1},{2,2,0,0}};
struct node{
	int x,y,lie;  //0直立,1横躺,2竖躺
}st,ed;
int n,m,dis[505][505][3];
char s[505][505];
queue<node> q;
bool Valid(int x,int y){
	return x>=1&&y>=1&&x<=n&&y<=m;
}
bool valid(node next){
	if(!Valid(next.x,next.y)) return false;
	if(s[next.x][next.y]=='#') return false;
	if(next.lie==0&&s[next.x][next.y]!='.') return false;
	if(next.lie==1&&s[next.x][next.y+1]=='#') return false;
	if(next.lie==2&&s[next.x+1][next.y]=='#') return false;
	return true;
}
void parse_st_ed(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s[i][j]=='O') ed.x=i,ed.y=j,ed.lie=0,s[i][j]=='.';
			else if(s[i][j]=='X'){
				for(int k=0;k<4;k++){
					int x=i+dx[k],y=j+dy[k];
					if(Valid(x,y)&&s[x][y]=='X'){
						st.x=min(i,x),st.y=min(j,y);
						st.lie=k<2?1:2;
						s[i][j]=s[x][y]='.';
						break;
					}
				}
				if(s[i][j]=='X') st.x=i,st.y=j,st.lie=0;
			}
		}
	}
}
int bfs(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<3;k++){
				dis[i][j][k]=-1;
			}
		}
	}
	while(q.size()) q.pop();
	dis[st.x][st.y][st.lie]=0;
	q.push(st);
	while(q.size()){
		node now=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			node next;
//			cout<<now.x<<' '<<now.y<<' '<<now.lie<<'\n';
			next.x=now.x+next_x[now.lie][i];
			next.y=now.y+next_y[now.lie][i];
			next.lie=next_lie[now.lie][i];
			if(!valid(next)) continue;
			if(dis[next.x][next.y][next.lie]==-1){
				dis[next.x][next.y][next.lie]=dis[now.x][now.y][now.lie]+1;
				q.push(next);
				if(next.x==ed.x&&next.y==ed.y&&next.lie==ed.lie) return dis[next.x][next.y][next.lie];
			}
		}
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m&&n&&m){
		for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
		parse_st_ed();
		int ans=bfs();
		if(ans==-1) printf("Impossible\n");
		else printf("%d\n",ans);
	}
	return 0;
}

蒟蒻实在找不出来错了,希望大佬帮忙指正。

2025/7/25 11:12
加载中...