Given a 2d-matrix mat[][] 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) we can go to cells (i, j + arr[i][j]) or (i + arr[i][j], j). We cannot go out of bounds. If no path exists then print -1.
Examples:
Input: mat[][] = {
{2, 1, 2},
{1, 1, 1},
{1, 1, 1}}
Output: 2
The path will be {0, 0} -> {0, 2} -> {2, 2}
Thus, we are reaching there in two steps.
Input: mat[][] = {
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Output: 4
Approach: We have already discussed a dynamic programming based approach for this problem in this article. This problem can also be solved using breadth first search (BFS).
The algorithm is as follows:
- Push (0, 0) in a queue.
- Traverse (0, 0) i.e. push all the cells it can visit in the queue.
- Repeat the above steps, i.e. traverse all the elements in the queue individually again if they have not been visited/traversed before.
- Repeat till we don’t reach the cell (N-1, N-1).
- The depth of this traversal will give the minimum steps required to reach the end.
Remember to mark a cell visited after it has been traversed. For this, we will use a 2D boolean array.
Why BFS works?
- This whole scenario can be considered equivalent to a directed graph where each cell is connected to at most two more cells({i, j+arr[i][j]} and {i+arr[i][j], j}).
- The graph is unweighted. BFS can find the shortest path in such scenarios.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define n 3using namespace std;// Function to return the minimum steps// required to reach the end of the matrixint minSteps(int arr[][n]){ // Array to determine whether // a cell has been visited before bool v[n][n] = { 0 }; // Queue for bfs queue<pair<int, int> > q; // Initializing queue q.push({ 0, 0 }); // To store the depth of search int depth = 0; // BFS algorithm while (q.size() != 0) { // Current queue size int x = q.size(); while (x--) { // Top-most element of queue pair<int, int> y = q.front(); // To store index of cell // for simplicity int i = y.first, j = y.second; q.pop(); // Base case if (v[i][j]) continue; // If we reach (n-1, n-1) if (i == n - 1 && j == n - 1) return depth; // Marking the cell visited v[i][j] = 1; // Pushing the adjacent cells in the // queue that can be visited // from the current cell if (i + arr[i][j] < n) q.push({ i + arr[i][j], j }); if (j + arr[i][j] < n) q.push({ i, j + arr[i][j] }); } depth++; } return -1;}// Driver codeint main(){ int arr[n][n] = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } }; cout << minSteps(arr); return 0;} |
Java
// Java implementation of the approach import java.util.*;import java.io.*;public class GFG{ static int n= 3 ;static class Pair{ int first , second; Pair(int a, int b) { first = a; second = b; }}// Function to return the minimum steps // required to reach the end of the matrix static int minSteps(int arr[][]) { // Array to determine whether // a cell has been visited before boolean v[][] = new boolean[n][n]; // Queue for bfs Queue<Pair> q = new LinkedList<Pair>(); // Initializing queue q.add(new Pair( 0, 0 )); // To store the depth of search int depth = 0; // BFS algorithm while (q.size() != 0) { // Current queue size int x = q.size(); while (x-->0) { // Top-most element of queue Pair y = q.peek(); // To store index of cell // for simplicity int i = y.first, j = y.second; q.remove(); // Base case if (v[i][j]) continue; // If we reach (n-1, n-1) if (i == n - 1 && j == n - 1) return depth; // Marking the cell visited v[i][j] = true; // Pushing the adjacent cells in the // queue that can be visited // from the current cell if (i + arr[i][j] < n) q.add(new Pair( i + arr[i][j], j )); if (j + arr[i][j] < n) q.add(new Pair( i, j + arr[i][j] )); } depth++; } return -1; } // Driver code public static void main(String args[]){ int arr[][] = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } }; System.out.println(minSteps(arr)); }}// This code is contributed by Arnab Kundu |
Python3
# Python 3 implementation of the approachn = 3# Function to return the minimum steps# required to reach the end of the matrixdef minSteps(arr): # Array to determine whether # a cell has been visited before v = [[0 for i in range(n)] for j in range(n)] # Queue for bfs q = [[0,0]] # To store the depth of search depth = 0 # BFS algorithm while (len(q) != 0): # Current queue size x = len(q) while (x > 0): # Top-most element of queue y = q[0] # To store index of cell # for simplicity i = y[0] j = y[1] q.remove(q[0]) x -= 1 # Base case if (v[i][j]): continue # If we reach (n-1, n-1) if (i == n - 1 and j == n - 1): return depth # Marking the cell visited v[i][j] = 1 # Pushing the adjacent cells in the # queue that can be visited # from the current cell if (i + arr[i][j] < n): q.append([i + arr[i][j], j]) if (j + arr[i][j] < n): q.append([i, j + arr[i][j]]) depth += 1 return -1# Driver codeif __name__ == '__main__': arr = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] print(minSteps(arr))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approach using System;using System.Collections.Generic; class GFG{ static int n= 3 ;public class Pair{ public int first , second; public Pair(int a, int b) { first = a; second = b; }}// Function to return the minimum steps // required to reach the end of the matrix static int minSteps(int [,]arr) { // Array to determine whether // a cell has been visited before Boolean [,]v = new Boolean[n,n]; // Queue for bfs Queue<Pair> q = new Queue<Pair>(); // Initializing queue q.Enqueue(new Pair( 0, 0 )); // To store the depth of search int depth = 0; // BFS algorithm while (q.Count != 0) { // Current queue size int x = q.Count; while (x-->0) { // Top-most element of queue Pair y = q.Peek(); // To store index of cell // for simplicity int i = y.first, j = y.second; q.Dequeue(); // Base case if (v[i,j]) continue; // If we reach (n-1, n-1) if (i == n - 1 && j == n - 1) return depth; // Marking the cell visited v[i,j] = true; // Pushing the adjacent cells in the // queue that can be visited // from the current cell if (i + arr[i,j] < n) q.Enqueue(new Pair( i + arr[i,j], j )); if (j + arr[i,j] < n) q.Enqueue(new Pair( i, j + arr[i,j] )); } depth++; } return -1; } // Driver code public static void Main(){ int [,]arr = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } }; Console.WriteLine(minSteps(arr)); }}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approachvar n = 3;// Function to return the minimum steps// required to reach the end of the matrixfunction minSteps(arr){ // Array to determine whether // a cell has been visited before var v = Array.from(Array(n), ()=> Array(n).fill(0)); // Queue for bfs var q = []; // Initializing queue q.push([0, 0 ]); // To store the depth of search var depth = 0; // BFS algorithm while (q.length != 0) { // Current queue size var x = q.length; while (x--) { // Top-most element of queue var y = q[0]; // To store index of cell // for simplicity var i = y[0], j = y[1]; q.shift(); // Base case if (v[i][j]) continue; // If we reach (n-1, n-1) if (i == n - 1 && j == n - 1) return depth; // Marking the cell visited v[i][j] = 1; // Pushing the adjacent cells in the // queue that can be visited // from the current cell if (i + arr[i][j] < n) q.push([ i + arr[i][j], j ]); if (j + arr[i][j] < n) q.push([i, j + arr[i][j] ]); } depth++; } return -1;}// Driver codevar arr = [ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ];document.write( minSteps(arr));</script> |
Output:
4
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
