0分求调!!!
查看原帖
0分求调!!!
1676730
ZBXAPCY楼主2025/7/21 20:11
#include<bits/stdc++.h>
using namespace std;
int n,m,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
char a[25][25],p[2][4]={{'N','S','W','E'},{'n','s','w','e'}};
struct node{
	int rsp,bsp,rx,ry,bx,by;
	string ans;
	bool operator<(const node &tht)const{
		if(bsp!=tht.bsp)
			return bsp>tht.bsp;
		return rsp>tht.rsp;
	}
};
bool d[25][25][25][25];
int main(){
	for(int k=1;;k++){
		bool ok=1;
		node o;
		o.rsp=o.bsp=0;
		o.ans="";
		memset(d,0,sizeof(d));
        cin>>n>>m;
		if(!n&&!m)return 0;
        for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
        	   	cin>>a[i][j]; 
        		if(a[i][j]=='S')
					o.rx=i,o.ry=j;
        		if(a[i][j]=='B')
					o.bx=i,o.by=j;
        	}
        printf("Maze #%d\n",k);
        d[o.rx][o.ry][o.bx][o.by]=1;
        priority_queue<node>q;
        q.push(o);
        while(q.size()){
            node o=q.top(),z;
            q.pop();
            int cx=o.rx,cy=o.ry;
			if(a[o.bx][o.by]=='T'){
				cout<<o.ans<<"\n\n";
				ok=0;
				break;
			}
            for(int i=0;i<4;i++){
                int nx=cx+dx[i],ny=cy+dy[i],bnx=o.bx,bny=o.by;
                if(nx<1||ny<1||nx>n||ny>m||a[nx][ny]=='#')
					continue;
				if(nx==bnx&&ny==bny){
    				bnx+=dx[i];bny+=dy[i];
					if(bnx<1||bny<1||bnx>n||bny>m||a[bnx][bny]=='#')
                        continue;
                    z.bsp=o.bsp+1;
					z.rsp=o.rsp+1;
					z.rx=nx;
					z.ry=ny;
                    z.bx=bnx;
					z.by=bny;
					z.ans=o.ans+p[0][i];
                }
				else{
					z.bsp=o.bsp;
					z.rsp=o.rsp+1;
					z.rx=nx;
					z.ry=ny;
					z.bx=bnx;
					z.by=bny;
					z.ans=o.ans+p[1][i];
				}
				if(d[nx][ny][bnx][bny])
					continue;
				d[nx][ny][bnx][bny]=1;
				q.push(z);
			}
        }
        if(ok)
			cout<<"Impossible\n\n";
    }
    return 0;
}
2025/7/21 20:11
加载中...