TLE请求dalao们帮助
查看原帖
TLE请求dalao们帮助
1275349
guoyangqwq楼主2024/3/14 20:20
#include<bits/stdc++.h>
using namespace std;
int t,n,m,f[1001][1001],dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1},p,minnow=INT_MAX;
char a[1001][1001];
string mins,st;
void dfs(int x,int y,string s,int now){
	now++;
	if(x==n&&y==m){
		p=1;
		if(now<minnow){
			minnow=now;
			mins=s;
		}
	}
	for(int i=1;i<=4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		st=s;
		if(a[xx][yy]==a[x][y]||xx<1||xx>n||yy<1||yy>m||f[xx][yy]==1)
		continue;
		if(i==1)st+="U";
		if(i==2)st+="R";
		if(i==3)st+="D";
		if(i==4)st+="L";
		f[xx][yy]=1;
		dfs(xx,yy,st,now);
		f[xx][yy]=0;
	}
	return ;
}
int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		cin>>a[i][j];
		f[1][1]=1;
		dfs(1,1,"",-1);
		if(p==0)
		cout<<-1<<endl;
		else {
			cout<<minnow<<endl;
			cout<<mins<<endl;
		}
		minnow=INT_MAX;
		mins="";
		p=0;
	}
	return 0;
}
2024/3/14 20:20
加载中...