样例过不去但80分,wa #1和#8,求助
查看原帖
样例过不去但80分,wa #1和#8,求助
947892
Khalil_Fong楼主2023/8/23 16:01
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=100;
int a[N][N];
struct re{
	int x;
	int y;
	int d;
	int step;
};
queue<re> q;
int fx[6][4]={{},{1,2,3},{0,0,0},{-1,-2,-3},{0,0,0}};
int fy[6][4]={{},{0,0,0},{-1,-2,-3},{0,0,0},{1,2,3}};
int ans=1e9;
bool vis[N][N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]==1){
				a[i][j-1]=a[i-1][j]=a[i-1][j-1]=1;
			}
		}
	};
	int sx,sy,zx,zy;
	cin>>sx>>sy>>zx>>zy;
	char c;
	cin>>c;
	if(sx==zx&&sy==zy){
		cout<<0;
		return 0;
	}
	if(a[sx][sy]==1||a[zx][zy]==1){
		cout<<-1;
		return 0;
	}
	int f;
	if(c=='S') f=1;//下 
	if(c=='W') f=2;//左 
	if(c=='N') f=3;//上 
	if(c=='E') f=4;//右
	vis[sx][sy][f]=1;
	q.push((re){sx,sy,f,0});
	while(!q.empty()){
		re x=q.front();
		q.pop();
		if(x.x==zx&&x.y==zy){
			ans=x.step;
			break;
		}
		for(int i=1;i<=4;i++){ 
			for(int j=0;j<3;j++){
				int tx=x.x+fx[i][j];
				int ty=x.y+fy[i][j];
				if(a[tx][ty]==1||tx<1||tx>=n||ty<1||ty>=m) break; 
				if(!vis[tx][ty][i]){
					if(x.d==i){//不转 
						vis[tx][ty][i]=1;
						q.push((re){tx,ty,i,x.step+1});
					}
					if(abs(x.d-i)==1||abs(x.d-i)==3){//转一下 
						vis[tx][ty][i]=1;
						q.push((re){tx,ty,i,x.step+2});
					}
					if(abs(x.d-i)==2){//转两下 
						vis[tx][ty][i]=1;
						q.push((re){tx,ty,i,x.step+3});
					}
				}
			}
		}
	}
	ans==1e9?cout<<-1:cout<<ans;
	return 0;
}
2023/8/23 16:01
加载中...