# DirectI coding Contest -Spiderman saves the victim

what is the approach for solving this problem. I have tried using floodfill and bfs using vector of pair. But first approach gives WA and second is giving RE.

My flood fill solution.

Solution

The problem can be solved by using Bfs … but first you need to construct the graph as per the given conditions …
solution on ideone

1 Like

It can be solved by both algorithms ,if you provide your solution may be I can correct you…
Your sol gives -1 on (1,1).I’v corrected it http://ideone.com/83TpJX

Your solution will be wrong in this test case :
It should give 0.

``````
1
3 3 1 1 2
1 2 3
6 9 4
7 8 5
``````

#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
long long test;
cin>>test;
while(test–)
{
long long m,n,x,y,d;
cin>>m>>n>>x>>y>>d;
long long a[m][n];
for(long long i=0;i<m;i++)
{
for(long long j=0;j<n;j++)
{
cin>>a[i][j];
}
}
long long b[m][n];
for(long long i=0;i<m;i++)
{
for(long long j=0;j<n;j++)
b[i][j]=-1;
}
b[0][0]=0;
queue<pair<int,long long > > q;
q.push(make_pair(0,0));
while(!q.empty())
{
long long x1=q.front().first;
long long y1=q.front().second;
q.pop();
long long abovex1=x1-1,abovey1=y1;
long long belowx1=x1+1,belowy1=y1;
long long leftx1=x1,lefty1=y1-1;
long long rightx1=x1,righty1=y1+1;
if(abovex1>=0 && abovex1<m && abovey1>=0 && abovey1<n && b[abovex1][abovey1]==-1 && fabs(a[abovex1][abovey1]-a[x1][y1])<=d)
{
q.push(make_pair(abovex1,abovey1));
b[abovex1][abovey1]=b[x1][y1]+1;
}
if(belowx1>=0 && belowx1<m && belowy1>=0 && belowy1<n && b[belowx1][belowy1]==-1&& fabs(a[belowx1][belowy1]-a[x1][y1])<=d)
{
q.push(make_pair(belowx1,belowy1));
b[belowx1][belowy1]=b[x1][y1]+1;
}
if(leftx1>=0 && leftx1<m && lefty1>=0 && lefty1<n && b[leftx1][lefty1]==-1&& fabs(a[leftx1][lefty1]-a[x1][y1])<=d)
{
q.push(make_pair(leftx1,lefty1));
b[leftx1][lefty1]=b[x1][y1]+1;
}
if(rightx1>=0 && rightx1<m && righty1>=0 && righty1<n && b[rightx1][righty1]==-1&& fabs(a[rightx1][righty1]-a[x1][y1])<=d)
{
q.push(make_pair(rightx1,righty1));
b[rightx1][righty1]=b[x1][y1]+1;
}
if(b[x-1][y-1]!=-1)
break;
}
if(b[x-1][y-1]==-1)
cout<<b[x-1][y-1]<<"\n";
else
cout<<b[x-1][y-1]-1<<"\n";
/*
for(long long i=0;i<n;i++)
{
for(long long j=0;j<m;j++)
{
cout<<b[i][j]<<"\t";
}
cout<<"\n";
}
*/
}
return 0;
}