调了半天都过不去
查看原帖
调了半天都过不去
599303
chenyihao2117楼主2023/8/5 14:50
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<utility>

using namespace std;

const int N=55;
struct Node{
	int x,y,dis;
	char p;
};
unordered_map<char,int> dx,dy,con;
unordered_map<char,char> le,ri;
int n,m,sx,sy,ex,ey;
char op;
int g[N][N];
bool state[N][N][4],st[N][N];

void init()
{
    memset(state,0,sizeof state);
	dx['N']=-1,dx['S']=1,dx['W']=0,dx['E']=0;
	dy['N']=0,dy['S']=0,dy['W']=-1,dy['E']=1;
	le['N']='W',le['W']='S',le['S']='E',le['E']='N';
	ri['W']='N',ri['S']='W',ri['E']='S',ri['N']='E';
	con['N']=0,con['W']=1,con['S']=2,con['E']=3;
}

int bfs(int x,int y)
{
	queue<Node> q;
	q.push({x,y,0,op});
	state[x][y][con[op]]=1;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		if(t.x==ex&&t.y==ey) return t.dis;
		
		int a,b;
		char c=t.p;
		bool flag=1;
		//操作1,2,3 
		for(int i=1;i<=3;i++)
		{
		    a=dx[t.p]*i+t.x,b=dy[t.p]*i+t.y;
		    if(a<1||a>=n||b<1||b>=m||st[a][b]) break;
		    if(state[a][b][con[t.p]]) break;
		    state[a][b][con[c]]=1;
		    q.push({a,b,t.dis+1,c});
		}
		//操作4
		c=le[t.p];
		if(!state[t.x][t.y][con[c]])
		{
		    q.push({t.x,t.y,t.dis+1,c});
		    state[t.x][t,y][con[c]]=1;
		}
		//操作5
		c=ri[t.p];
		if(!state[t.x][t.y][con[c]])
		{
		    q.push({t.x,t.y,t.dis+1,c});
		    state[t.x][t.y][con[c]]=1;
		}
	}
	
	return -1;
}

int main()
{
	init();
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>g[i][j];
			if(g[i][j]==1)
			{
				st[i][j]=1;
				st[i-1][j]=1;
				st[i-1][j-1]=1;
				st[i][j-1]=1;
			}
		}
	cin>>sx>>sy>>ex>>ey>>op;
	
	int ans=bfs(sx,sy);
	cout<<ans;
	
	return 0;
}

第6个点过不去

2023/8/5 14:50
加载中...