SIMMIN-Editorial

Problem Link

Practice
Contest

Setter & Tester : Akashdeep

Difficulty

Easy

Prerequisites

BFS, DP

Problem

Given a Matrix M*N and Starting point (Xs,Ys). You Can Move in Up (i,j-1), Down (i+1, j), Right (i, j+1), and Left (i-1, j) direction to reach the final point (Xf,Yf), but the Condition is you can only move on indices having similar numbers and in minimum steps.

Quick Explanation

• Check every direction with similar numbers from the starting point.
• Store the steps in a matrix to reach those points.
• Check all neighboring similar numbers till no one is left.

Explanation

Implementation

Use a standard Breath-First Search (BFS) algorithm from the starting cell i.e. (Xs, Ys) of matrix i.e. matrix[n][m], and enqueue the index of this cell in the queue. Initialize a matrix i.e. dis[n][m] with INT_MAX to store the steps. Iterate while the queue is not empty and perform the following operations:

i) Dequeue the cell present at the front of the queue i.e (kx,ky).
ii) Move to its adjacent cells i.e. (x,y) and check if the value inside the dis[x][y]== INT_MAX and value inside the matrix[x][y]==matrix[Xs][Ys] then update the dis[x][y] = dis[kx][ky] + 1 to store the steps to reach (x, y) from (kx, ky) and enqueue the cell i.e. (x,y) into the queue.

Finally print the dis[Xf][Yf] if not INT_MAX else print -1;

Time Complexity

The time complexity is O(n*m) where n, m is the number of rows and columns.

Solution

Setter's Solution
#include<bits/stdc++.h> 
using namespace std;
#define mod 1000000007 
typedef long long int ll;
void solve(); 
int main() { 
     ios_base::sync_with_stdio(false);cin.tie(NULL); 
   
     #ifndef ONLINE_JUDGE 
     freopen("input.txt", "r", stdin); 
     freopen("error.txt", "w", stderr); 
     freopen("output.txt", "w", stdout); 
     #endif 
     ll t;
     cin>>t;
     while(t--){
      solve(); 
     }

     cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
     return 0; 
} 

//condition for point inside the matrix
bool isInsidematrix(int i, int j,int row,int col) { 
return (i >= 0 && i < row && j >= 0 && j < col);
}


void solve(){

    int row;
    int col;
    cin>>row>>col;
    int matrix[row][col];
    for(int i=0;i<row;i++){
     for(int j=0;j<col;j++){
          cin>>matrix[i][j];
     }
    }
    int initialx,initialy,finalx,finaly;
    cin>>initialx>>initialy>>finalx>>finaly;

    int dis[row][col];


     //initilize all step distance to INT_MAX
     for (int i = 0; i < row; i++){
          for (int j = 0; j < col; j++){
               dis[i][j] = INT_MAX;
          }
     }

     //all possible directions
     int dx[] = {-1, 0, 1, 0};
     int dy[] = {0, 1, 0, -1};

     queue<pair<int, int>> st;

     //insert initial cell
     st.push({initialx, initialy});
     //intital position path distance
     dis[initialx][initialy] = 0;
     //loop until queue gets empty
     while (st.size())
     {
     //pop cell from queue
       int kx = st.front().first, ky = st.front().second;
       st.pop();
     //check up down right left direction w.r.t. current cell k
          for (int i = 0; i < 4; i++)
          {
               int x = kx + dx[i];
               int y = ky + dy[i];

     //check whether x y is inside the matrix or not
               if (!isInsidematrix(x, y,row,col))
                    {  
                         continue;}

               if (dis[x][y] == INT_MAX && matrix[x][y] == matrix[initialx][initialy])
               {
     //store steps in dis[x][y] and push the neigbouring cells
                    dis[x][y] = dis[kx][ky] + 1;
                    st.push({x, y});
               }
          }
     }
    
     //print number of steps
     cout << (dis[finalx][finaly] == INT_MAX ? -1 : dis[finalx][finaly]) << "\n";
}

Feel free to share your approach. Suggestions are welcomed as always.

3 Likes

Hi! Can you pls tell me where I am going wrong Solution: 48062417 | CodeChef . It will be of great help

Check your answer when the initial and final points are the same

I have updated it Solution: 48075745 | CodeChef , it is still not working

Try these testcases:
2
2 2
1 2
1 1
0 0 0 1
2 5
1 1 2 1 1
2 1 1 1 2
0 0 0 4

In the constraints, it is mentioned that 1 <= A[i][j] , so it shouldn’t be 0…

it’s not working properly in this case!! Why?