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;
}

Can anyone provide the question link please?

could you suggest me a test case n which floodfill would fail whereas bfs would work?

it depends on your implementation of flood fill , if it is done through dfs it might be wrong … as you need to find the shortest distance in this graph which could be solved using either bfs or dijkstra but dfs doesn’t guarantee the shortest distance.