Timelimit exceeding in case 5

#1

#include<bits/stdc++.h>
using namespace std;
int c=0;
void print (int s[][1000],int n,int m)
{
if(c==0)
{ c++;
for(int i=0;i<n;i++)
{

        for (int j=0;j<m;j++)
        {

            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }
}

}

bool maze(char a[1000][1000],int s[][1000],int i,int j,int n,int m)
{
if(i==n-1 && j==m-1)
{
s[n-1][m-1]=1;
print(s,n,m);

	return true;


}
if(i>n || j>m)
{
    return false;
}
if(a[i][j]=='X')
{
    return false;
}
s[i][j]=1;
bool right=maze(a,s,i,j+1,n,m);
bool down=maze(a,s,i+1,j,n,m);

s[i][j]=0;

if(right||down)
{
    return true;
}

return false;

}

int main()
{
int n,m;
cin>>n>>m;
char a[1000][1000];
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
int s[1000][1000]={0};
bool ans=maze(a,s,0,0,n,m);
if(ans==false)
{
cout<<"-1";
}
return 0;
}

#2

@rakshitgangwar
Consider the case when you code already found a valid path in the first recursive call you made for the right path. It still goes on to check a valid path on the downside. Even though this path is not printed even after being found, the fact remains that time is wasted to search for it needlessly. Instead implement a condition to return if the first call returns true.
bool right = maze(a, s, i, j + 1, n, m);
if ( right )
return true;

#3

I tired it but still its not working

#4

@rakshitgangwar
Increase your array sizes from 1000 to 1005.

#5

Still Test case 5 is showing time-limit error.

#6

@rakshitgangwar
I simply made the above two changes and submitted it. I got a full score with it. If you are still facing any issues , share your latest code and the problem link you are trying to submit it on.

#7

#include<bits/stdc++.h>
using namespace std;
int c=0;
void print (int s[][1005],int n,int m)
{
if(c==0)
{
c++;
for(int i=0;i<n;i++)
{

        for (int j=0;j<m;j++)
        {

            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }
}

}

bool maze(char a[1005][1005],int s[][1005],int i,int j,int n,int m)
{
if(i==n-1 && j==m-1)
{
s[n-1][m-1]=1;
print(s,n,m);

	return true;


}
if(i>n || j>m)
{
    return false;
}
if(a[i][j]=='X')
{
    return false;
}
s[i][j]=1;
bool right=maze(a,s,i,j+1,n,m);
if(right)
{
    return true;
}
bool down=maze(a,s,i+1,j,n,m);
s[i][j]=0;
return false;

}

int main()
{
int n,m;
cin>>n>>m;
char a[1005][1005];
for (int i=0;i<n;i++)
{
for (int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
int s[1005][1005]={0};
maze(a,s,0,0,n,m);
if(c==0)
{
cout<<"-1";
}
return 0;
}

#8

@rakshitgangwar
You forgot to check for down.
if(down)
return true;

#9

I did that also. Nevermind i figured it out myself. Thank you.