Getting WA in MAKEMAZE problem. Tried all test cases and checked all constraints. Still WA.
Here's the code
> #include<bits/stdc++.h>
using namespace std;
long long int n,m;
char graph[1000][1000];
long long int count1;
long long int move_x[4]={0,0,1,-1};
long long int move_y[4]={1,-1,0,0};
long long int vis[3000][3000];
long long int t;
int counter[1000][1000]={0};
queue<pair<long long int,long long int> > que;
int check(int x,int y)
{
if(x>=0 && x<n && y>=0 &&y<m)
return 1;
return 0;
}
int dfs(int x,int y)
{
vis[x][y]=1;
int i,j,k,tx,ty;
for(i=0;i<4;i++)
{
tx=x+move_x[i];
ty=y+move_y[i];
if(!check(tx,ty) || vis[tx][ty])
continue;
if(graph[tx][ty]=='.')
{
dfs(tx,ty);
}
}
}
int main()
{
scanf("%d",&t);
for(long long int r=0;r<t;r++)
{
while(!que.empty())
{
que.pop();
}
scanf("%d%d",&n,&m);
for(long long int i=0;i<n;i++)
{
for(long long int j=0;j<m;j++)
{
cin>>graph[i][j];
vis[i][j]=0;
}
}
count1=0;
if(n==1)
{
for(int i=0;i<m;i++)
{
if(graph[0][i]=='.')
{
count1++;
que.push(make_pair(0,i));
}
}
if(count1>2||count1<2)
{
printf("invalid\n");
continue;
}
}
else
{
if(m==1)
{
for(int i=0;i<n;i++)
{
if(graph[i][0]=='.')
{
count1++;
que.push(make_pair(i,0));
}
}
if(count1>2||count1<2)
{
printf("invalid\n");
continue;
}
}
else
{
for(long long int j=0;j<m;j++)
{
if(graph[0][j]=='.')
{
count1++;
que.push(make_pair(0,j));
}
if(graph[n-1][j]=='.')
{
count1++;
que.push(make_pair(n-1,j));
}
}
for(long long int i=0;i<n;i++)
{
if(graph[i][0]=='.')
{
count1++;
que.push(make_pair(i,0));
}
if(graph[i][m-1]=='.')
{
count1++;
que.push(make_pair(i,m-1));
}
}
if(count1>2||count1<2)
{
printf("invalid\n");
continue;
}
}
}
pair<long long int,long long int> pr=que.front();
long long int x=pr.first;long long int y=pr.second;
dfs(x,y);
que.pop();
pr=que.front();
long long int x1=pr.first;long long int y1=pr.second;
if(vis[x1][y1]==1)
{
printf("valid\n");
}
else
printf("invalid\n");
}
return 0;
}