CHEF AND FRIENDSHIP -SEPT004- EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
DIFFICULTY
EASY-MEDIUM
PREREQUISITES
Array, Vector, Queue , Searching
PROBLEM
Given a matrix (GRID) of size NxM , where N is the number of rows and M is thenumber of columns. The matrix has
0 and 1 as its cells . 0 represents a barrier and chef cannot pass through a barrier. Our chef is stuck at a position
in grid with co-ordinates (i,j) and wants to reach his friend , the co-ordinate (a,b) where his friend is waiting for
him. Chef can either move left, right, down or up. Each step takes 1 sec to travel. Chef wants to visit and spend time
with his friend. Chef has a busy schedule ahead. His Friend spends X time with him. Find the minimum time after which
chef will be free or if chef cannot visit his friend.
EXPLANATION
We are given with a binary array (1s and 0s) of dimension NxM .The friend spends X time with him.The initial position of
the chef and the position of his friend is given.The chef has to reach his friend. In the array 0 is blocked and chef can
pass through 1.The chef takes 1 unit of time to pass from one cell to another.We have to find minimum time requird by
chef to meet his friend.We will be using BFS lgorithm to solve this problem
BFS(Breadth First Search) algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the
next vertex to start a search, when a dead end occurs in any iteration.It considers all the paths starting from the
source and moves ahead one unit in all those paths at the same time which makes sure that the first time when the
the destination is visited, it is the shortest path.
Example Text Case
Input:
5 5 3
1 1 0 1 0
0 1 1 0 1
1 0 1 1 0
1 1 0 1 1
0 1 0 0 1
0 0
3 4
Output:
10
In the above example,initially the chef is at (0,0) and has to reach (3,4).
step 1:(0,0) → (0,1)
step 2:(0,1) → (1,1)
step 3:(1,1) → (1,2)
step 4:(1,2) → (2,2)
step 5:(2,2) → (2,3)
step 6:(2,3) → (3,3)
step 7:(3,3) → (3,4)
So, 7 unit of time.And he has to spend 3 unit of time with his friend.Hence it is 7+3=10
So the minimum time required is time required to reach his friend plus the time he has to spend with his friend.
Condition:Chef can only move up,down,left,right.Cross way motion is not allowed.
SOLUTION
Setter's Solution
/*CODE STARTS HERE*/
#include<bits/stdc++.h>
#define ll long long int
#define str string
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define vvi vector<vector<ll>>
#define vi vector<ll>
#define mapii map<ll,ll>
#define mapvi map<vector<ll>,ll>
#define mapiv map<ll,vector<ll>>
#define all(a) (a).begin(),(a).end()
#define show(arr,n) for(ll i=0;i<n;i++)cout<<arr[i]<<" ";
#define pii pair<ll,ll>
#define repi(x,n) for(ll i=x;i<n;++i)
#define repid(x,n) for(ll i=x-1;i>=n;--i)
#define repj(x,n) for(ll j=x;j<n;++j)
#define repjd(x,n) for(ll j=x-1;j>=n;--j)
#define print2(x,y) cout<<x<<" "<<y<<'\n'
#define print3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n'
#define input(x) cin>>x
#define input2(x,y) cin>>x>>y
#define print(x) cout<<x<<'\n'
#define endl '\n'
#define M 1000000007
#define S 200005
const ll INF = 1ll<<60;
using namespace std;
ll bfs(vvi &grid,ll i,ll j,ll m,ll n,ll a,ll b)
{
queue<pair<ll,ll>>q;
vvi vis(n,vi(m,0));
q.push({i,j});
vis[i][j]=1;
vi dir={-1,0,1,0,-1};
ll count=0;
while(!q.empty())
{
ll size=q.size();
for(ll k=0;k<size;k++)
{
ll row=q.front().ff;
ll col=q.front().ss;
q.pop();
for(ll i=0;i<4;i++)
{
ll nrow=row+dir[i];
ll ncol=col+dir[i+1];
if(nrow<0 or ncol<0 or nrow>=n or ncol>=m or vis[nrow][ncol]==1 or grid[nrow][ncol]==0)continue;
vis[nrow][ncol]=1;
q.push({nrow,ncol});
if(nrow==a and ncol==b)return count+1;
}
}
count+=1;
}
return -1;
}
int main(){
ll n,m,x;
input(n);
input(m);
input(x);
vvi grid(n,vi(m));
ll in;
repi(0,n)
{
repj(0,m)
{
input(in);
grid[i][j]=in;
}
}
//print(grid[3][2]);
ll i,j;
ll a,b;
input2(i,j);
input2(a,b);
ll check=bfs(grid,i,j,m,n,a,b);
if (check==-1)print(-1);
else
print(x+check);
return 0;
}
/CODE ENDS HERE/