50pts 5WA 求调(附注释)
查看原帖
50pts 5WA 求调(附注释)
332488
Wind_Journey楼主2022/7/27 11:44

有5个WA,不知道是哪里出错了,改了一上午了也没改好,求大佬帮调!

#include <bits/stdc++.h>
using namespace std;
const int N=30;
struct node{
	int xn,yn,xe,ye,t,turnn,turnr;
	node(){}
	node(int _xn,int _yn,int _xe,int _ye,int _t,int _turnn,int _turnr){
		xn=_xn,yn=_yn,xe=_xe,ye=_ye,t=_t,turnn=_turnn,turnr=_turnr;
	}
};
//0-上 1-右 2-下 3-左(顺时针)
queue<node> b;
int vis[N][N][4][N][N][4],n,turn[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
char a[N][N];   
int ope(int a){
    a=max(a,1);//边界判断(防止越界)
    a=min(a,n);
    return a;
}
void print(node a){
    cout<<a.xn<<" "<<a.yn<<"  "<<a.xe<<" "<<a.ye<<"  "<<a.t<<"  "<<a.turnn<<" "<<a.turnr<<endl;
    return;
}
int bfs(){
	b.push(node(n,1,n,1,0,0,1));
	while(!b.empty()){
		node u=b.front();
		b.pop();
        print(u);
        if(u.xn==1&&u.yn==n&&u.xe==1&&u.ye==n) return u.t;//如果都回到终点则返回
		int riturn1=(u.turnn+1)%4,riturn2=(u.turnr+1)%4;//向右转
		if(!vis[u.xn][u.yn][riturn1][u.xe][u.ye][riturn2]){//若当前状态没有被访问过
			node temp=u;
			temp.turnn=riturn1,temp.turnr=riturn2,temp.t=u.t+1;
			vis[u.xn][u.yn][riturn1][u.xe][u.ye][riturn2]=1;//更新
			b.push(temp);//入队
		}
		int leturn1=(u.turnn+3)%4,leturn2=(u.turnr+3)%4;//向左转
		if(!vis[u.xn][u.yn][leturn1][u.xe][u.ye][leturn2]){//同上
			node temp=u;
			temp.turnn=leturn1,temp.turnr=leturn2,temp.t=u.t+1;
			vis[u.xn][u.yn][leturn1][u.xe][u.ye][leturn2]=1;
			b.push(temp);
		}
		int xxn=ope(u.xn+turn[u.turnn][0]),yyn=ope(u.yn+turn[u.turnn][1]),xxe=ope(u.xe+turn[u.turnr][0]),yye=ope(u.ye+turn[u.turnr][1]);//定义前进一步后的状态
        if(u.xn==1&&u.yn==n){xxn=u.xn,yyn=u.yn;}
        if(u.xe==1&&u.ye==n){xxe=u.xe,yye=u.ye;}//如果有牛已经走到终点则不再走(回到终点的状态)
		if(!vis[xxn][yyn][u.turnn][xxe][yye][u.turnr]){//未走过
            if(a[xxn][yyn]!='H'&&a[xxe][yye]!='H'){//且无障碍
                b.push(node(xxn,yyn,xxe,yye,u.t+1,u.turnn,u.turnr));
                vis[xxn][yyn][u.turnn][xxe][yye][u.turnr]=1;
            }
        }
        if(!vis[xxn][yyn][u.turnn][u.xe][u.ye][u.turnr]&&a[xxe][yye]=='H'){//2有障碍只动1
            b.push(node(xxn,yyn,u.xe,u.ye,u.t+1,u.turnn,u.turnr));
            vis[xxn][yyn][u.turnn][u.xe][u.ye][u.turnr]=1;
        }
        if(!vis[u.xn][u.yn][u.turnn][xxe][yye][u.turnr]&&a[xxn][yyn]=='H'){//1有障碍只动2
            b.push(node(u.xn,u.yn,xxe,yye,u.t+1,u.turnn,u.turnr));
            vis[u.xn][u.yn][u.turnn][xxe][yye][u.turnr]=1;
        }
	}
    return -1;
}
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	cout<<bfs();
	return 0;
}

2022/7/27 11:44
加载中...