DCP-3: Maze Tester(why timelimit) please help

Dev Skill archived problems can be discussed here.

DCP-3: Maze Tester(why timelimit) please help

by Subhashis » Tue Mar 07, 2017 4:07 am

#include<bits/stdc++.h>
using namespace std;
long dx[]= {-1,0,0,1};
long dy[]= {0,-1,1,0};
char s[50][50];
long vis[50][50]={0},flag,cnt=0;
long bfs(long x,long y)
{
long x1,y1,i1;
vis[x][y]=1;
for(i1=0;i1<4;i1++)
{
x1=x+dx[i1];
y1=y+dy[i1];
if((vis[x1][y1]==0)&&(x1>=0&&x1<30)&&(y1>=0&&y1<30)&&((s[x1][y1]=='.')||(s[x1][y1]=='G')))
{
cnt++;
if(s[x1][y1]=='G')
{
flag=1;
break;
}
if(cnt>900)
break;
vis[x1][y1]=1;
bfs(x1,y1);
}
}
return flag;
}
main()
{
while(1)
{
long i,j,k=-1,k1=-1,y=0,n=0;
for(i=0; i<30; i++)
{
scanf("%s",s[i]);
for(j=0;j<strlen(s[i]);j++)
{
if(s[i][j]=='P')
{
y=1;
k=i;
k1=j;
}
if(s[i][j]=='G')
{
n=1;
k=i;
k1=j;
}
vis[i][j]=0;
}
}
long ans=0;
cnt=0,flag=0;
if(y==1&&n==1)
ans=bfs(k,k1);
else
ans=0;
if(ans==1)
{
printf("Possible\n");
}
else
printf("Impossible\n");
}
}
 
Posts: 2
Joined: Tue Mar 07, 2017 3:06 am

Who is online
Users browsing this forum: No registered users and 2 guests
cron