Chef Loves Mangoes Editorial

editorial
1

PROBLEM LINK:

Chef Loves Mangoes

Author: mugdha273
Editorialist: mugdha273

DIFFICULTY:

MEDIUM-HARD

PROBLEM:

Given a matrix, find minimum number of "d"s you need to take to make a path from:

  • last “b” to atleast one “f” and “w”
  • last “f” to ateast one “w” and “b”
  • last “w” to atleast one “b” and “f”
    all three conditons must satisfy
    last = row-wise last found. Where you are allowed to move up/down/right or left.

Prerequisites:

  • knowledge of BFS

EXPLANATION:

The solution uses a modified BFS (Breadth-First Search) algorithm to find the minimum distance from each starting point to other types of gardens minimum one time.

Initializes a 3D array “dis” to store the distances of all points from each of the three starting points. It then finds the three starting points and pushes them to a deque “q” to initialize the BFS and to make sure that algorithm runs at least one time for each starting possible starting point.

The BFS algorithm is called three times for each starting point in the deque. For each point in the deque, the algorithm checks all its adjacent points and updates their distances if necessary. The deque is used to ensure that the we explore “b” “f” or “w” cell first which might be our answer in the end.

After finding the distances from all starting points to all points in the garden, the code calculates the minimum distance required to visit all three types of mango trees at least once while avoiding the “s” cells. It does so by iterating over all points in the garden and adding the distances from each starting point to that point. If the point is a “d” cell, the distance is added only once. After succesfully fillig this “dis” array, we finally go into the loop to find the minimum path approachable from each type of garden to succesfully join all three of them.

I’d suggest take a look over the code as it has some nice comments for better explanation ;).

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>

using namespace std;

int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
const long long N = 1e3 + 5, INF = INT_MAX, MOD = 1e9 + 7;

int n,m;
char arr[N][N];     //stores the type of garden at each cell in the grid

//store the minimum distance from each type of garden to all other cells in the grid.
int dis[3][N][N];

//basic queue for bfs
deque <pair<int,int>> q;

bool valid(int i , int j){
   return i >= 0 && i < n && j >= 0 && j < m && arr[i][j] != 's';
}

void bfs(int type){
   // the distance to reach the starting cell is 0 (initalizing it basically)
   dis[type][q.front().first][q.front().second] = 0;

   while (!q.empty()){
       pair<int,int> fr = q.front();
       q.pop_front();

       for (int i = 0; i < 4; ++i) {
           int nx = fr.first + dx[i];
           int ny = fr.second + dy[i];
           if (valid(nx,ny)){
               // whether the distance to reach the current cell ((nx, ny)) through the current node ((fr.first, fr.second)) is less than the previously calculated distance to reach that cell (dis[turn][nx][ny]).
               if (dis[type][fr.first][fr.second] + (arr[nx][ny] == 'd') < dis[type][nx][ny]){

                   //increase the distance by 1 if the current cell is "d"
                   dis[type][nx][ny] = dis[type][fr.first][fr.second] + (arr[nx][ny] == 'd');
                   if (arr[nx][ny] == 'd') q.emplace_back(nx,ny);
                   //if it is "b" "f" pr "w", keep it in the front of the queue so that it can be explored at better priority
                   else q.emplace_front(nx,ny);
               }
           }
       }
   }

}

void solve(){
   cin >> n >> m;
   for (int i = 0; i < n; ++i) {
       for (int j = 0; j < m; ++j) {
           for (int k = 0; k < 3; ++k) {
               dis[k][i][j] = 1e8;
           }
       }
   }
   vector <pair<int,int>> store(3);
   for (int i = 0; i < n; ++i) {
       for (int j = 0; j < m; ++j) {
           cin >> arr[i][j];
           if (arr[i][j] == 'b'){
               store[0] = make_pair(i, j);
           }
           if (arr[i][j] == 'f'){
               store[1] = make_pair(i, j);
           }
           if (arr[i][j] == 'w'){
               store[2] = make_pair(i, j);
           }
       }
   }
   //make sure the algotrithm runs atleast once for "b", "f" and "w"
   q.emplace_front(store[0]);
   bfs(0);
   q.emplace_front(store[1]);
   bfs(1);
   q.emplace_front(store[2]);
   bfs(2);
   int ans = 1e8;

   //pick the least one
   for (int i = 0; i < n; ++i) {
       for (int j = 0; j < m; ++j) {
           if (arr[i][j] != 's')
               ans = min(ans,(dis[0][i][j] + dis[1][i][j] + dis[2][i][j] - 2 * (arr[i][j] == 'd')));
       }
   }
   if (ans < 1e7) cout << ans;
   else cout << -1;
}

int main() {
// 	freopen("input.in", "r", stdin);
// 	freopen("output.out", "w", stdout);
   ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   int t = 1;
   //cin >> t;
   while (t--) {
       solve();
   }
}
1 Like