有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;
}