10pts,求调!玄关
查看原帖
10pts,求调!玄关
907430
corner_xiejunqi楼主2024/12/21 11:32
#include<bits/stdc++.h>
using namespace std;
int n,m;
int g[100][100],vis[101][101][3];
int sx,sy,ex,ey;
char direction;
inline int dir(char a){
	if(a=='N') return 0;
	else if(a=='E') return 1;
	else if(a=='S') return 2;
	else return 3;
}
struct node{
	int x,y,dir,ans;
};
queue<node> q;
int xx,yy;
inline void find(int x,int y,int d,int step){
	if(d==0) yy=y+step;
	else if(d==1) xx=x+step;
	else if(d==2) yy=y-step;
	else xx=x-step;
	return;
}
int right1,left1;
signed main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int whether;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>whether;
			g[i][j]=g[i+1][j]=g[i][j+1]=g[i+1][j+1]=whether;
		}
	cin>>sx>>sy>>ex>>ey>>direction;
	n++;m++;
	int dirs=dir(direction);
	sx++;sy++;ex++;ey++;
	q.push({sx,sy,dirs,0});	
	int ans=0x3f3f3f3f;    
	while(!q.empty()){
		node now=q.front();
		vis[now.x][now.y][now.dir]=1;
		q.pop();
		if(now.x==ex && now.y==ey){
			ans=min(ans,now.ans);
			continue;
		}
		left1=(now.dir==0?3:(now.dir-1));
		right1=(now.dir==3?0:(now.dir+1));
		for(int i=1;i<=3;i++){
			find(now.x,now.y,now.dir,i);
			if(!vis[xx][yy][now.dir] && xx>=1 && yy>=1 && xx<=n && yy<=m && !g[xx][yy]) q.push({xx,yy,now.dir,now.ans+1});
			find(now.x,now.y,left1,i);
			if(!vis[xx][yy][left1] && xx>=1 && yy>=1 && xx<=n && yy<=m && !g[xx][yy]) q.push({xx,yy,left1,now.ans+2});
			find(now.x,now.y,right1,i);
			if(!vis[xx][yy][right1] && xx>=1 && yy>=1 && xx<=n && yy<=m && !g[xx][yy]) q.push({xx,yy,right1,now.ans+2});
			if(!vis[now.x][now.y][right1]) q.push({now.x,now.y,right1,now.ans+1});
			if(!vis[now.x][now.y][left1]) q.push({now.x,now.y,left1,now.ans+1});
		}
	}
	cout<<ans;
	return 0;
}

2024/12/21 11:32
加载中...