Introduction
The problem statement is: Given a matrix M[][], and an integer K, we need to find the length of the shortest path from the top-left cell to the bottom-right cell of the matrix. The constraint is: the difference between the neighbouring elements must not exceed “K”.
Example 1
Input
M[][] =
{
{1, 2, -19, 0},
{2, 5, 6, -3},
{11, 13, 5, 1},
{8, 9, 10, 4}
}
K = 5
Output:
6
Explanation:
The shortest path following the given constraint is 1 -> 2 -> 5 -> 6 -> 5 -> 1 -> 4. The length of this path is 6.

Solution approach
Idea: The idea is pretty simple. We run a BFS where we enqueue the adjacent elements only when the difference between the current element and the adjacent element is <= K.
Algorithm:
- Maintain a queue “Q” and a VISITED array, dimensions of which are equal to the given matrix.
- Insert the top-left node into the Q and mark VISITED[0][0] = true.
-
Now, while Q is not empty, do the following:
-
Pop from the Q. The node provides us with three pieces of information:
- Row index = i
- Column index = j
- Steps = length of the shortest path from (0,0) to (i, j)
- Check if the node corresponds to the bottom left node, i.e. i==(R - 1) and j==(C-1), where R and C are the numbers of rows and columns, respectively. Suppose this is the case return Steps.
-
Else, iterate through all of its adjacent nodes (4-way connected) and do the following:
- Let us denote an adjacent cell by M[next_i][next_j]. If the cell lies within the boundaries of the matrix and it is not VISITED i.e. VISITED[next_i][next_j] = FALSE and | M[i][j] - M[next_i][next_j] | <= K then push the node {next_i, next_j, Steps + 1} into the Q and mark it as VISITED. Note we increased the number of Steps by 1. This signifies that this node may possibly be included in the shortest path.
- If (i) doesn’t hold, just skip.
-
Pop from the Q. The node provides us with three pieces of information:
- If anything is not returned in the above loop, just return -1. This means that there does not exist any path with the given constraints.
C++ Code implementation:
#include <bits/stdc++.h>
using namespace std;
int shortestPath(vector<vector<int>> &m, int K)
{
int r = m.size();
// If the matrix is empty, return 0
if (r == 0)
{
return 0;
}
int c = m[0].size();
/*
Declaring queue, this is the main data structure
that help us to perform a BFS
*/
queue<tuple<int, int, int>> q;
/*
The first value in the tuple: row index (i)
The second value in the tuple: column index (j)
The third value in the tuple: length of the shortest path from (0,0) to (i,j)
*/
/*
Declaring a visited array to hold the
information of which nodes are already
visited
*/
vector<vector<bool>> visited(r, vector<bool>(c, false));
q.push(make_tuple(0, 0, 0));
visited[0][0] = true;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
/*
Run a conditional bfs, we only
push an element in the queue if the difference
doesn't exceed K
*/
while (not q.empty())
{
// Extracting a node from the front of the queue
auto [i, j, steps] = q.front();
q.pop();
/*
If the node corresponds to the bottom-right cell
we return steps, which is our answer
*/
if (i == r - 1 and j == c - 1)
{
return steps;
}
// Iterate over the adjacent cells
for (int p = 0; p < 4; p++)
{
int next_i = i + di[p];
int next_j = j + dj[p];
// Check if the cell lies within the boundaries of the matrix
if (next_i >= 0 and next_i < r and next_j >= 0 and next_j < c)
{
/*
Check if the node is already visited and the
difference between the nodes in <= K
*/
if (not visited[next_i][next_j] and abs(m[i][j] - m[next_i][next_j]) <= K)
{
q.push(make_tuple(next_i, next_j, steps + 1));
visited[next_i][next_j] = true;
}
}
}
}
// If there is no path possible, return -1
return -1;
}
int main()
{
vector<vector<int>> m{
{1, 2, -19, 0},
{2, 5, 6, -3},
{11, 13, 5, 1},
{8, 9, 10, 4}};
cout << shortestPath(m, 5);
}
Output:
6