Minimum steps required to reach the end of a matrix | Set 2 | Java implementation of the approach ; Function to return the minimum steps required to reach the end of the matrix ; Array to determine whether a cell has been visited before ; Queue for bfs ; Initializing queue ; To store the depth of search ; BFS algorithm ; Current queue size ; Top - most element of queue ; To store index of cell for simplicity ; Base case ; If we reach ( n - 1 , n - 1 ) ; Marking the cell visited ; Pushing the adjacent cells in the queue that can be visited from the current cell ; Driver code
import java . util . * ; class GFG { static int n = 3 ; static class Pair { int first , second ; Pair ( int a , int b ) { first = a ; second = b ; } } static int minSteps ( int arr [ ] [ ] ) { boolean v [ ] [ ] = new boolean [ n ] [ n ] ; Queue < Pair > q = new LinkedList < Pair > ( ) ; q . add ( new Pair ( 0 , 0 ) ) ; int depth = 0 ; while ( q . size ( ) != 0 ) { int x = q . size ( ) ; while ( x -- > 0 ) { Pair y = q . peek ( ) ; int i = y . first , j = y . second ; q . remove ( ) ; if ( v [ i ] [ j ] ) continue ; if ( i == n - 1 && j == n - 1 ) return depth ; v [ i ] [ j ] = true ; 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 ; } public static void main ( String args [ ] ) { int arr [ ] [ ] = { { 1 , 1 , 1 } , { 1 , 1 , 1 } , { 1 , 1 , 1 } } ; System . out . println ( minSteps ( arr ) ) ; } }