50分求条
查看原帖
50分求条
1014060
yyc_hzdebaba楼主2025/7/21 14:35
#include<bits/stdc++.h>
using namespace std;
int n,m,l[505][505][5],ans;
char c[505][505];
struct op{
    int x,y,po;
}qd,zd;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const int ne_x[5][5]={{-2,1,0,0},{-1,1,0,0},{-1,2,0,0}};
const int ne_y[5][5]={{0,0,-2,1},{0,0,-1,2},{0,0,-1,1}};
const int ne_po[5][5]={{2,2,1,1},{1,1,0,0},{0,0,2,2}};
queue<op>q;
bool check(op yu){
    if(yu.x<1 || yu.x>n || yu.y<1 || yu.y>m)return false;
    if(c[yu.x][yu.y]=='#')return false;
    if(yu.po==0 && c[yu.x][yu.y]!='.')return false;
    if(yu.po==1 && c[yu.x][yu.y+1]=='#')return false;
    if(yu.po==2 && c[yu.x+1][yu.y]=='#')return false;
    return true;
}
int main(){
    while(1){
        cin>>n>>m;
        if(!n && !m)break;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>c[i][j];
                if(c[i][j]=='O')zd.x=i,zd.y=j,zd.po=0,c[i][j]='.';
                if(c[i][j]=='X'){
                    for(int k=0;k<4;k++){
                        int fx=i+dx[k],fy=j+dy[k];
                        if(fx>=1 && fx<=n && fy>=1 && fy<=m && c[fx][fy]=='X'){
                            qd.x=min(i,fx),qd.y=min(j,fy);
                            qd.po=(j<2? 2:1);
                            c[i][j]='.',c[fx][fy]='.';
                        }
                    }
                    if(c[i][j]=='X')qd.x=i,qd.y=j,qd.po=0;
                }
            }
        }
        ans=-1;
        memset(l,0,sizeof(l));
        while(q.size())q.pop();
        l[qd.x][qd.y][qd.po]=1,q.push(qd);
        while(q.size()){
            op w=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                op rp;
                rp.x=w.x+ne_x[w.po][i],rp.y=w.y+ne_y[w.po][i],rp.po=ne_po[w.po][i];
                if(!check(rp))continue;
                if(!l[rp.x][rp.y][rp.po]){
                    l[rp.x][rp.y][rp.po]=l[w.x][w.y][w.po]+1;
                    q.push(rp);
                    if(rp.x==zd.x && rp.y==zd.y && rp.po==zd.po){
                        ans=l[rp.x][rp.y][rp.po];
                        break;
                    }
                }
            }
            if(ans>=0)break;
        }
        if(ans>=0)cout<<ans-1<<endl;
        else cout<<"Impossible"<<endl;
    }
    return 0;
}
2025/7/21 14:35
加载中...