I have been trying to solve the Grid Path Construction problem on CSES.
The link to the question: GRID PATH CONSTUCTION
This was my code to the above question:
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,n) for(ll i=a;i<n;i++)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define v vector
char moves[]={‘L’,‘R’,‘D’,‘U’};
int dx[]={0,0,1,-1};
int dy[]= {-1,1,0,0};
bool is_safe(vector<vector >vis,int x1,int y1,int n,int m)
{
return (x1>=0)&&(x1<n)&&(y1>=0)&&(y1<m)&&(!vis[x1][y1]);
}
string recurse(vector<vector >&vis,int x1,int y1,int x2,int y2,int &len,string &temp,int n,int m)
{
vis[x1][y1]=true;
len++;
if(len==nm&&x1==x2&&y1==y2)
return temp;
if(len==nm)
return “p”;
if(x1==x2&&y1==y2)
return “p”;
for(int i=0;i<4;i++)
{
if(is_safe(vis,x1+dx[i],y1+dy[i],n,m))
{
temp.pb(moves[i]);
string lala=recurse(vis,x1+dx[i],y1+dy[i],x2,y2,len,temp,n,m);
if(lala!=“p”)
return lala;
temp.erase(temp.begin()+temp.size()-1);
vis[x1+dx[i]][y1+dy[i]]=false;
len–;
}
}
return “p”;
}
void solve()
{
int n,m,x1,y1,x2,y2,len=0;
cin>>n>>m>>x1>>y1>>x2>>y2;
vector<vector >vis(n,vector(m,false));
string temp;
x1–;x2–;y1–;y2–;
string ans=recurse(vis,x1,y1,x2,y2,len,temp,n,m);
if(ans==“p”)
cout<<“NO”<<endl;
else
cout<<“YES\n”<<ans<<endl;
}
int main()
{
fast;
ll t;
cin>>t;
while(t–)
{
solve();
}
return 0;
}
Could anyone provide a further optimization to the question because the above code times out for 8/17 test cases.