TLE 求优化
查看原帖
TLE 求优化
1063855
xu_zhihao楼主2024/4/6 18:26
#include<bits/stdc++.h>
using namespace std;
long long  n,m;
struct node
{
	string p;
	long long  num;
	long long  x;
	long long  y;
};
queue<node>q;
void clear(queue<node>& q)
{
    queue<node> empty;
    swap(empty, q);
}
string s[2010];
long long  tx[]={0,0,-1,1};
long long  ty[]={1,-1,0,0};
string r[]={"R","L","U","D"};
long long  d[2010][2010];
string ret;
long long  mn=1e9;
void bfs()
{
	mn=1e9;
	for(long long  i=0;i<n;i++)
	{
		for(long long  j=0;j<m;j++)
		{
			d[i][j]=0;
		}
	}
	d[0][0]=1;
	q.push({"",0,0,0});
	while(!q.empty())
	{
		auto f=q.front();q.pop();
		if(f.x==n-1 && f.y==m-1)
		{
			mn=f.num;
			ret=f.p;
			break;
		}
		//cout<<f.num<<endl;
		for(long long  i=0;i<4;i++)
		{
			long long  fx=f.x+tx[i];
			long long  fy=f.y+ty[i];
			if(fx>=0 && fx<n && fy>=0 && fy<m)
			{
				if(s[fx][fy]!=s[f.x][f.y])
				{
					if(!d[fx][fy])
					{
						string op=f.p;
						d[fx][fy]=1;
						op+=r[i];
						q.push({op,f.num+1,fx,fy});
					}
				}
			}
		}
	}
	clear(q);
	if(mn==1e9)
	{
		cout<<-1;
	}
	else
	{
		cout<<mn<<endl<<ret;
	}
	if(!(n==1 && m==1))cout<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	long long  t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(long long  i=0;i<n;i++)
		{
	        cin>>s[i];
		}
		bfs();
	}
}

QAQ

2024/4/6 18:26
加载中...