help 感觉想法没错,但是样例没过
查看原帖
help 感觉想法没错,但是样例没过
127169
Baiwhiter楼主2021/5/21 22:11
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=55;
int mov[]={0,1,2,3,-1,-1,-1,-1,-1,-1};
int g[N][N],vis[N][N][5];
int res=1e9;
int stx,sty,edx,edy,p;
char point;
int n,m;
struct posi{
	int x,y,to,tot;
};
int main(){
	memset(vis,0,sizeof(vis));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&g[i]);
		}
	}
	
	cin>>stx>>sty>>edx>>edy;
	cin>>point;
	if(point=='E'){
		p=1;
	}else if(point=='S'){
		p=2;
	}else if(point=='W'){
		p=3;
	}else p=4;
	
	vis[stx][sty][p]=1;
	queue<posi> q;
	posi st;
	st.x=stx,st.y=sty,st.to=p,st.tot=0;
	q.push(st);
	while(!q.empty()){
		posi now;
		now=q.front(),q.pop();
		if(now.x==edx && now.y==edy){
			res=min(res,now.tot);
			//cout<<now.tot<<endl;
		}
		int nowp=now.to,nowt=now.tot,nxtp;//nowp是当前指向,nowt是当前的指令数,nxtp是下一个指向 
		for(int i=1;i<=10;i++){
			//cout<<i<<endl;
			posi nxt;//下一个更新的节点 
			nxtp=nowp;//下一个节点指向先等于当前节点指向 
			//cout<<nxtp<<endl;
			if(i>=4 && i<=6){
				if(nowp==1) nxtp=4;
				else nxtp-=1;
				nxt.x=now.x;
				nxt.y=now.y;
			}//left
			if(i>=7 && i<=9){
				if(nowp==4) nxtp=1;
				else nxtp+=1;
				nxt.x=now.x;
				nxt.y=now.y;
			}//right			//先考虑转向再考虑移动 
			if(i<=3){
				if(nxtp==1){//E
					nxt.x=now.x;
					nxt.y=now.y+mov[i];
				}else if(nxtp==2){//S
					nxt.x=now.x+mov[i];
					nxt.y=now.y;				
				}else if(nxtp==3){//W
					nxt.x=now.x;
					nxt.y=now.y-mov[i];				
				}else if(nxtp==4){//N
					nxt.x=now.x-mov[i];
					nxt.y=now.y;			
				}				
			}
			//cout<<nxtp<<endl;
			if(vis[nxt.x][nxt.y][nxtp]) continue;
			if(nxt.x<1 || nxt.x>n || nxt.y<1 || nxt.y>m || g[nxt.x][nxt.y]) continue;
			//cout<<nxt.x<<" "<<nxt.y<<endl;
			nxt.to=nxtp;nxt.tot=nowt+1;
			vis[nxt.x][nxt.y][nxtp]=1;
			q.push(nxt);
		}
	}
	if(res==1e9)
		cout<<-1<<endl;
	else cout<<res<<endl;
	return 0;
}
2021/5/21 22:11
加载中...