Problem Link
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.