Find minimum steps required to reach the end of a matrix | Set 2
Given a 2D matrix consisting of positive integers, the task is to find the minimum number of steps required to reach the end of the matrix. If we are at cell (i, j) then we can go to all the cells represented by (i + X, j + Y) such that X ? 0, Y ? 0 and X + Y = arr[i][j]. If no path exists then print -1.
Examples:
Input: arr[][] = {
{4, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Output: 1
The path will be from {0, 0} -> {2, 2} as manhattan distance
between two is 4.
Thus, we are reaching there in 1 step.Input: arr[][] = {
{1, 1, 2},
{1, 1, 1},
{2, 1, 1}}
Output: 3
A simple solution will be to explore all possible solutions which will take exponential time.
An efficient solution is to use dynamic programming to solve this problem in polynomial time. Lets decide the states of dp.
Let’s say we are at cell (i, j). We will try to find the minimum number of steps required to reach the cell (n – 1, n – 1) from this cell.
We have arr[i][j] + 1 possible path.
The recurrence relation will be
dp[i][j] = 1 + min(dp[i][j + arr[i][j]], dp[i + 1][j + arr[i][j] – 1], …., dp[i + arr[i][j]][j])
To reduce the number of terms in recurrence relation, we can put an upper bound on the values of X and Y. How?
We know that i + X < N. Thus, X < N – i otherwise they would go out of bounds.
Similarly, Y < N – j
0 ? Y < N – j …(1)
X + Y = arr[i][j] …(2)
Substituting value of Y from second into first, we get
X ? arr[i][j] + j – N + 1
From above we get another lower bound on constraint of X i.e. X ? arr[i][j] + j – N + 1.
So, new lower bound on X becomes X ? max(0, arr[i][j] + j – N + 1).
Also X ? min(arr[i][j], N – i – 1).
Our recurrence relation optimizes to
dp[i][j] = 1 + min(dp[i + max(0, arr[i][j] + j – N + 1)][j + arr[i][j] – max(0, arr[i][j] + j – N + 1)], …., dp[i + min(arr[i][j], N – i – 1)][j + arr[i][j] – min(arr[i][j], N – i – 1)])
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <bits/stdc++.h>
#define n 3
using namespace std;
// 2d array to store
// states of dp
int dp[n][n];
// Array to determine whether
// a state has been solved before
int v[n][n];
// Function to return the minimum steps required
int minSteps(int i, int j, int arr[][n])
{
// Base cases
if (i == n - 1 and j == n - 1)
return 0;
if (i > n - 1 || j > n - 1)
return 9999999;
// If a state has been solved before
// it won't be evaluated again
if (v[i][j])
return dp[i][j];
v[i][j] = 1;
dp[i][j] = 9999999;
// Recurrence relation
for (int k = max(0, arr[i][j] + j - n + 1);
k <= min(n - i - 1, arr[i][j]); k++) {
dp[i][j] = min(dp[i][j], minSteps(i + k, j + arr[i][j] - k, arr));
}
dp[i][j]++;
return dp[i][j];
}
// Driver code
int main()
{
int arr[n][n] = { { 4, 1, 2 },
{ 1, 1, 1 },
{ 2, 1, 1 } };
int ans = minSteps(0, 0, arr);
if (ans >= 9999999)
cout << -1;
else
cout << ans;
return 0;
}
// Java implementation of the approach
class GFG {
static int n = 3;
// 2d array to store
// states of dp
static int[][] dp = new int[n][n];
// Array to determine whether
// a state has been solved before
static int[][] v = new int[n][n];
// Function to return the minimum steps required
static int minSteps(int i, int j, int arr[][])
{
// Base cases
if (i == n - 1 && j == n - 1) {
return 0;
}
if (i > n - 1 || j > n - 1) {
return 9999999;
}
// If a state has been solved before
// it won't be evaluated again
if (v[i][j] == 1) {
return dp[i][j];
}
v[i][j] = 1;
dp[i][j] = 9999999;
// Recurrence relation
for (int k = Math.max(0, arr[i][j] + j - n + 1);
k <= Math.min(n - i - 1, arr[i][j]); k++) {
dp[i][j] = Math.min(dp[i][j],
minSteps(i + k, j + arr[i][j] - k, arr));
}
dp[i][j]++;
return dp[i][j];
}
// Driver code
public static void main(String[] args)
{
int arr[][] = { { 4, 1, 2 },
{ 1, 1, 1 },
{ 2, 1, 1 } };
int ans = minSteps(0, 0, arr);
if (ans >= 9999999) {
System.out.println(-1);
}
else {
System.out.println(ans);
}
}
}
// This code contributed by Rajput-Ji
# Python3 implementation of the approach
import numpy as np
n = 3
# 2d array to store
# states of dp
dp = np.zeros((n,n))
# Array to determine whether
# a state has been solved before
v = np.zeros((n,n));
# Function to return the minimum steps required
def minSteps(i, j, arr) :
# Base cases
if (i == n - 1 and j == n - 1) :
return 0;
if (i > n - 1 or j > n - 1) :
return 9999999;
# If a state has been solved before
# it won't be evaluated again
if (v[i][j]) :
return dp[i][j];
v[i][j] = 1;
dp[i][j] = 9999999;
# Recurrence relation
for k in range(max(0, arr[i][j] + j - n + 1),min(n - i - 1, arr[i][j]) + 1) :
dp[i][j] = min(dp[i][j], minSteps(i + k, j + arr[i][j] - k, arr));
dp[i][j] += 1;
return dp[i][j];
# Driver code
if __name__ == "__main__" :
arr = [
[ 4, 1, 2 ],
[ 1, 1, 1 ],
[ 2, 1, 1 ]
];
ans = minSteps(0, 0, arr);
if (ans >= 9999999) :
print(-1);
else :
print(ans);
# This code is contributed by AnkitRai01
// C# implementation of the approach
using System;
class GFG
{
static int n = 3;
// 2d array to store
// states of dp
static int[,] dp = new int[n, n];
// Array to determine whether
// a state has been solved before
static int[,] v = new int[n, n];
// Function to return the minimum steps required
static int minSteps(int i, int j, int [,]arr)
{
// Base cases
if (i == n - 1 && j == n - 1)
{
return 0;
}
if (i > n - 1 || j > n - 1)
{
return 9999999;
}
// If a state has been solved before
// it won't be evaluated again
if (v[i, j] == 1)
{
return dp[i, j];
}
v[i, j] = 1;
dp[i, j] = 9999999;
// Recurrence relation
for (int k = Math.Max(0, arr[i,j] + j - n + 1);
k <= Math.Min(n - i - 1, arr[i,j]); k++)
{
dp[i,j] = Math.Min(dp[i,j],
minSteps(i + k, j + arr[i,j] - k, arr));
}
dp[i,j]++;
return dp[i,j];
}
// Driver code
static public void Main ()
{
int [,]arr = { { 4, 1, 2 },
{ 1, 1, 1 },
{ 2, 1, 1 } };
int ans = minSteps(0, 0, arr);
if (ans >= 9999999)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(ans);
}
}
}
// This code contributed by ajit.
// Javascript implementation of the approach
let n = 3;
// 2d array to store
// states of dp
let dp = new Array(n);
// Array to determine whether
// a state has been solved before
let v = new Array(n);
for(let i = 0; i < n; i++)
{
dp[i] = new Array(n);
v[i] = new Array(n);
for(let j = 0; j < n; j++)
{
dp[i][j] = 0;
v[i][j] = 0;
}
}
// Function to return the minimum steps required
function minSteps(i, j, arr)
{
// Base cases
if (i == n - 1 && j == n - 1) {
return 0;
}
if (i > n - 1 || j > n - 1) {
return 9999999;
}
// If a state has been solved before
// it won't be evaluated again
if (v[i][j] == 1) {
return dp[i][j];
}
v[i][j] = 1;
dp[i][j] = 9999999;
// Recurrence relation
for (let k = Math.max(0, arr[i][j] + j - n + 1);
k <= Math.min(n - i - 1, arr[i][j]); k++) {
dp[i][j] = Math.min(dp[i][j],
minSteps(i + k, j + arr[i][j] - k, arr));
}
dp[i][j]++;
return dp[i][j];
}
let arr = [ [ 4, 1, 2 ],
[ 1, 1, 1 ],
[ 2, 1, 1 ] ];
let ans = minSteps(0, 0, arr);
if (ans >= 9999999) {
console.log(-1);
}
else {
console.log(ans);
}
Output
1
Time Complexity: O(n3).
Auxiliary Space: O(n*n)
Using Breadth-First Search (BFS)
This solution employs Breadth-First Search (BFS) to explore the shortest path through the matrix based on the constraints given. By utilizing a queue to process each cell iteratively and systematically, we ensure that we explore all possible paths in the shortest steps order:
Follow the steps to solve the problem:
- Queue for BFS: Cells are processed in FIFO order to ensure the minimum number of steps is explored first.
- Visited Matrix: To keep track of the minimum steps taken to reach each cell and avoid unnecessary reprocessing.
- Iterative Exploration: For each cell, explore all potential moves according to the value of the cell, adhering to the boundary conditions.
Below is the implementation of above approach:
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int minimumSteps(vector<vector<int> >& matrix)
{
int n = matrix.size();
if (n == 0) {
return -1;
}
// Matrix to store steps taken to reach each cell
vector<vector<int> > steps(n, vector<int>(n, INT_MAX));
queue<pair<int, int> > q;
q.push({ 0, 0 });
steps[0][0] = 0;
// BFS to explore all possible moves
while (!q.empty()) {
auto cell = q.front();
q.pop();
int i = cell.first, j = cell.second;
int stepCount = steps[i][j];
int moveLimit = matrix[i][j];
// Explore all valid moves from the current cell
for (int dx = 0; dx <= moveLimit; dx++) {
int dy = moveLimit - dx;
int ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
if (stepCount + 1 < steps[ni][nj]) {
steps[ni][nj] = stepCount + 1;
q.push({ ni, nj });
}
}
}
}
// Check the bottom-right corner for the result
int result = steps[n - 1][n - 1];
return result != INT_MAX ? result : -1;
}
int main()
{
vector<vector<int> > matrix1
= { { 4, 1, 2 }, { 1, 1, 1 }, { 2, 1, 1 } };
cout << minimumSteps(matrix1)
<< endl; // Output should be 1
return 0;
}
import java.util.LinkedList;
import java.util.Queue;
public class MinimumSteps {
public static int minimumSteps(int[][] matrix)
{
int n = matrix.length;
if (n == 0) {
return -1;
}
// Matrix to store steps taken to reach each cell
int[][] steps = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
steps[i][j] = Integer.MAX_VALUE;
}
}
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] { 0, 0 });
steps[0][0] = 0;
// BFS to explore all possible moves
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int i = cell[0], j = cell[1];
int stepCount = steps[i][j];
int moveLimit = matrix[i][j];
// Explore all valid moves from the current cell
for (int dx = 0; dx <= moveLimit; dx++) {
int dy = moveLimit - dx;
int ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < n && nj >= 0
&& nj < n) {
if (stepCount + 1 < steps[ni][nj]) {
steps[ni][nj] = stepCount + 1;
queue.add(new int[] { ni, nj });
}
}
}
}
// Check the bottom-right corner for the result
int result = steps[n - 1][n - 1];
return result != Integer.MAX_VALUE ? result : -1;
}
public static void main(String[] args)
{
int[][] matrix1
= { { 4, 1, 2 }, { 1, 1, 1 }, { 2, 1, 1 } };
System.out.println(
minimumSteps(matrix1)); // Output should be 1
}
}
from collections import deque
def minimum_steps(matrix):
n = len(matrix)
if n == 0:
return -1
# Matrix to store steps taken to reach each cell
steps = [[float('inf')] * n for _ in range(n)]
queue = deque([(0, 0)])
steps[0][0] = 0
# BFS to explore all possible moves
while queue:
i, j = queue.popleft()
step_count = steps[i][j]
move_limit = matrix[i][j]
# Explore all valid moves from the current cell
for dx in range(move_limit + 1):
dy = move_limit - dx
ni, nj = i + dx, j + dy
if 0 <= ni < n and 0 <= nj < n:
if step_count + 1 < steps[ni][nj]:
steps[ni][nj] = step_count + 1
queue.append((ni, nj))
# Check the bottom-right corner for the result
result = steps[n-1][n-1]
return result if result != float('inf') else -1
# Example usage
matrix1 = [[4, 1, 2], [1, 1, 1], [2, 1, 1]]
print(minimum_steps(matrix1)) # Output should be 1
function minimumSteps(matrix) {
const n = matrix.length;
if (n === 0) {
return -1;
}
// Matrix to store steps taken to reach each cell
const steps = new Array(n).fill(null).map(() => new Array(n).fill(Infinity));
const queue = [[0, 0]];
steps[0][0] = 0;
// BFS to explore all possible moves
while (queue.length > 0) {
const [i, j] = queue.shift();
const stepCount = steps[i][j];
const moveLimit = matrix[i][j];
// Explore all valid moves from the current cell
for (let dx = 0; dx <= moveLimit; dx++) {
const dy = moveLimit - dx;
const ni = i + dx, nj = j + dy;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
if (stepCount + 1 < steps[ni][nj]) {
steps[ni][nj] = stepCount + 1;
queue.push([ni, nj]);
}
}
}
}
// Check the bottom-right corner for the result
const result = steps[n - 1][n - 1];
return result !== Infinity ? result : -1;
}
// Example usage
const matrix1 = [[4, 1, 2], [1, 1, 1], [2, 1, 1]];
console.log(minimumSteps(matrix1)); // Output should be 1
// This code is contributed by SHIVAM GUPTA
Output
1
Time Complexity: O(n^2 * d), where n is the dimension of the matrix and d represents the maximum value in the matrix dictating the number of possible moves from each cell. In worst-case scenarios, each cell could potentially queue up other cells around it proportional to its value.
Auxilary Space: O(n^2), mainly for the storage of the steps matrix and the BFS queue, which in the worst case might need to hold all cells.
Contact Us