70pts
查看原帖
70pts
670349
laybare_mushroom楼主2024/10/10 18:49
#include<bits/stdc++.h>
using namespace std;
int n,m,a[55][55],vis[55][55],xx1,yy1,xx2,yy2,fang,kl=0;
char feng;
struct pp{
	int x,y,time,fang1;
};
std::queue<pp>q;
pp u;
pp u1;
pp md;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			if(a[i][j]==1){
				a[i-1][j]=1;
				a[i][j-1]=1;
				a[i-1][j-1]=1;
				vis[i-1][j]=1;
				vis[i][j-1]=1;
				vis[i-1][j-1]=1;
				vis[i][j]=1;
			} 
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0||j==0||i==n||j==m){
				a[i][j]=1;
				vis[i][j]=1;
			}
		//cout<<a[i][j];
		}
//	cout<<endl;
	}
//	cout<<endl;
	cin>>xx1>>yy1>>xx2>>yy2>>feng;
	if(a[xx1][yy1]==1||vis[xx1][yy1]==1){
		cout<<-1;
		return 0;
	}
	if(xx1==xx2&&yy1==yy2){
		cout<<0;
		return 0;
	}
	if(feng=='N'){
		fang=1;
	}
	if(feng=='S'){
		fang=2;
	}
	if(feng=='W'){
		fang=3;
	}
	if(feng=='E'){
		fang=4;
	}
	pp st;
	st.x=xx1,st.y=yy1,st.time=0,st.fang1=fang;
	q.push(st);
	vis[xx1][yy1]=1;
	vis[xx2][yy2]=-10;
	while(!q.empty()){
		u1=q.front();
//	cout<<u1.x<<" "<<u1.y<<" ";
		q.pop();
		vis[u1.x][u1.y]=1;
		a[u1.x][u1.y]=1;
	if(u1.x+1<n){	
		if(vis[u1.x+1][u1.y]!=1&&a[u1.x+1][u1.y]!=1){
			if(u1.fang1==2&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.time=u1.time;
				u.fang1=u1.fang1;
				//q.push(u);
				kl=-12;
			}
			if(u1.fang1==1&&kl!=-12){
                u.x=u1.x;
				u.y=u1.y;
				u.fang1 =2;
				u.time=u1.time+2;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==3&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =2;
			    u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==4&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =2;
				u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			kl=0;
					for(int j=1;j<=3;j++){
						if(j==1){
							pp md;
							md.x=u.x+1;md.y=u.y;md.fang1=2;md.time=u.time+1;
							q.push(md);
							if(vis[md.x][md.y]==-10){
								cout<<md.time;
								return 0;
							}
						}
						else{
							if(u.x+j<n){
							if(vis[u.x+j][u.y]==1||a[u.x+j][u.y]==1){
								break;
							}
								if(vis[u.x+j][u.y]!=1&&a[u.x+j][u.y]!=1){
								
									md.x=u.x+j;md.y=u.y;md.fang1=2;md.time=u.time+1;
									if(vis[md.x][md.y]==-10){
								cout<<md.time;
								return 0;
							}
									q.push(md);

							}
								
						}
					}
				}
			}
		}
	if(u1.x-1>0){
		if(vis[u1.x-1][u1.y]!=1&&a[u1.x-1][u1.y]!=1){
			if(u1.fang1==1&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.time=u1.time;
				u.fang1=u1.fang1;
				//q.push(u);
				kl=-12;
			}
			if(u1.fang1==2&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =1;
				u.time=u1.time+2;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==3&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =1;
			    u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==4&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =1;
			    u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			kl=0;
			for(int j=1;j<=3;j++){
						if(j==1){
							pp md;
							md.x=u.x-1;md.y=u.y;md.fang1=u.fang1;md.time=u.time+1;
							vis[u.x-1][u.y]=1;
							q.push(md);
							if(vis[md.x][md.y]==-10){
								cout<<md.time;
								return 0;
							}
						}
						else{
							if(u.x-j>0){
							if(vis[u.x-j][u.y]==1||a[u.x-j][u.y]==1){
								break;
							}
								if(vis[u.x-j][u.y]!=1&&a[u.x-j][u.y]!=1){
								
									md.x=u.x-j;md.y=u.y;md.fang1=u.fang1;md.time=u.time+1;
									if(vis[md.x][md.y]==-10){
								cout<<md.time;
								return 0;
							}
									q.push(md);
							}
							
						}
					}
				}
			}
		}
	if(u1.y+1<m){
		if(vis[u1.x][u1.y+1]!=1&&a[u1.x][u1.y+1]!=1){
			if(u1.fang1==4&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.time=u1.time;
				u.fang1=u1.fang1;
				//q.push(u);
				kl=-12;
			}
			if(u1.fang1==3&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =4;
				u.time=u1.time+2;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==1&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =4;
				u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==2&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =4;
				u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			kl=0;
				for(int j=1;j<=3;j++){
						if(j==1){
							pp md;
							md.x=u.x;md.y=u.y+1;md.fang1=u.fang1;md.time=u.time+1;
							if(vis[md.x][md.y]==-10){
								cout<<md.time;
								return 0;
							}
//																							if(md.x==7&&md.y==3){
//								cout<<"&&";
//							}
							q.push(md);
						}
						else{
							if(u.y+j<n){
							if(vis[u.x][u.y+j]==1||a[u.x][u.y+j]==1){
								break;
							}
								if(vis[u.x][u.y+j]!=1&&a[u.x][u.y+j]!=1){
								
									md.x=u.x;md.y=u.y+j;md.fang1=u.fang1;md.time=u.time+1;
									if(vis[md.x][md.y]==-10){
								cout<<md.time;
								return 0;
							
							}
							
									q.push(md);	
							}
							
						}
					}
				}
			}
		}
		if(u1.y-1>0){
			
			if(vis[u1.x][u1.y-1]!=1&&a[u1.x][u1.y-1]!=1){
				if(u1.fang1 ==3&&kl!=-12){
					u.x=u1.x;
				u.y=u1.y;
				u.time=u1.time;
				u.fang1=u1.fang1;
				//q.push(u);
				kl=-12;
			}
			if(u1.fang1==4&&kl!=-12){
				u.fang1 =3;
				u.time=u1.time+2;
				u.x=u1.x;
				u.y=u1.y;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==2&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =3;
				u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			if(u1.fang1==1&&kl!=-12){
				u.x=u1.x;
				u.y=u1.y;
				u.fang1 =3;
				u.time=u1.time+1;
				q.push(u);
				kl=-12;
			}
			kl=0;
					for(int j=1;j<=3;j++){
						if(j==1){
							pp md;
							md.x=u.x;md.y=u.y-1;md.fang1=u.fang1;md.time=u.time+1;
							if(vis[md.x][md.y]==-10){
							cout<<md.time;
								return 0;
							}
							q.push(md);
						}
						if(j==2||j==3){
							if(u.y-j>=0){
							if(vis[u.x][u.y-j]==1||a[u.x][u.y-j]==1){
								break;
							}
								if(vis[u.x][u.y-j]!=1&&a[u.x][u.y-j]!=1){
									md.x=u.x;md.y=u.y-j;md.fang1=u.fang1;md.time=u.time+1;
									if(vis[md.x][md.y]==-10){
							cout<<md.time;
								return 0;
							} 
							q.push(md);
							}
							
						}
					}
				}
			}
		}
	
	}
	cout<<-1;
	return 0;
} 


















2024/10/10 18:49
加载中...