#9#10MLE(O2)、RE+MLE(无O2)求助)
查看原帖
#9#10MLE(O2)、RE+MLE(无O2)求助)
190485
CH_mengxiang楼主2023/11/21 17:03
#include<bits/stdc++.h>
namespace mainCode{
using namespace std;
const int E=0,W=1,N=2,S=3,L=0,R=1;
bool e[51][51],book[51][51][4];
int n,m,x1,y1,x2,y2,fir;
struct pos
{
	int x,y,time,dir;
};
int change(int now,int type)
{
	int ans;
	if (type==L)
	{
		if (now==E) ans=N;
		else if (now==W) ans=S;
		else if (now==S) ans=E;
		else if (now==N) ans=W;
	}
	else
	{
		if (now==E) ans=S;
		else if (now==W) ans=N;
		else if (now==S) ans=W;
		else if (now==N) ans=E;
	}
	return ans;
}
int bfs()
{
	if (x1==x2&&y1==y2) return 0;
	queue<pos> q;
	q.push({x1,y1,0,fir});
	book[x1][y1][fir]=1;
	while (!q.empty())
	{
		pos now=q.front();
		int x=now.x,y=now.y,t=now.time,d=now.dir;
//		cout<<"[DEBUG]x="<<x<<" y="<<y<<" t="<<t<<" d="<<d<<endl;
		q.pop();
		for (int k=1;k<=5;k++)
		{
			if (k<=3)
			{
				if (d==E)
				{
					bool flag=1;
					for (int i=1;i<=k;i++)
						if (y+i>m||e[x][y+i])
						{
							flag=0;
							break;
						}
					if (!flag) continue;
					if (x==x2&&y+k==y2) return t+1;
					book[x][y+k][d]=1;
					q.push({x,y+k,t+1,d});
				}
				else if (d==W)
				{
					bool flag=1;
					for (int i=1;i<=k;i++)
						if (y-i<1||e[x][y-i])
						{
							flag=0;
							break;
						}
					if (!flag) continue;
					if (x==x2&&y-k==y2) return t+1;
					book[x][y-k][d]=1;
					q.push({x,y-k,t+1,d});
				}
				else if (d==N)
				{
					bool flag=1;
					for (int i=1;i<=k;i++)
						if (x-i<1||e[x-i][y])
						{
							flag=0;
							break;
						}
					if (!flag) continue;
					if (x-k==x2&&y==y2) return t+1;
					book[x-k][y][d]=1;
					q.push({x-k,y,t+1,d});
				}
				else
				{
					bool flag=1;
					for (int i=1;i<=k;i++)
						if (x+i>n||e[x+i][y])
						{
							flag=0;
							break;
						}
					if (!flag) continue;
					if (x+k==x2&&y==y2) return t+1;
					book[x+k][y][d]=1;
					q.push({x+k,y,t+1,d});
				}
			}
			else
			{
				int td=change(d,k-4);
				if (!book[x][y][td])
				{
					book[x][y][td]=1;
					q.push({x,y,t+1,td});
				}
			}
		}
	}
	return -1;
}
void main()
{
	cin>>n>>m;
	n--,m--;
	for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)
		{
			int x;
			cin>>x;
			if (x==1) e[i][j]=e[i+1][j]=e[i][j+1]=e[i+1][j+1]=1;
		}
	char c;
	cin>>x1>>y1>>x2>>y2>>c;
	if (c=='E') fir=E;
	else if (c=='W') fir=W;
	else if (c=='N') fir=N;
	else fir='S';
	cout<<bfs();
}
}//namespace mainCode;
signed main()
{ 
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	mainCode::main();
	return 0;
}

2023/11/21 17:03
加载中...