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 topleft cell to the bottomright 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 topleft 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==(C1), 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 (4way 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 bottomright 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