# SIMMIN-Editorial

Setter & Tester : Akashdeep

Easy

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 CodeChef: Practical coding for everyone . It will be of great help

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

I have updated it CodeChef: Practical coding for everyone , 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?