Minimum steps to reach any of the boundary edges of a matrix | Set 1 | C # program to find Minimum steps to reach any of the boundary edges of a matrix ; Function to find out minimum steps ; boundary edges reached ; already had a route through this point , hence no need to re - visit ; visiting a position ; vertically up ; horizontally right ; horizontally left ; vertically down ; minimum of every path ; Function that returns the minimum steps ; index to store the location at which you are standing ; find '2' in the matrix ; Initialize dp matrix with - 1 ; Initialize vis matrix with false ; Call function to find out minimum steps using memoization and recursion ; if not possible ; Driver Code
using System ; class Solution { static int r = 4 , c = 5 ; static int findMinSteps ( int [ , ] mat , int n , int m , int [ , ] dp , bool [ , ] vis ) { if ( n == 0 || m == 0 || n == ( r - 1 ) || m == ( c - 1 ) ) { return 0 ; } if ( dp [ n , m ] != - 1 ) return dp [ n , m ] ; vis [ n , m ] = true ; int ans1 , ans2 , ans3 , ans4 ; ans1 = ans2 = ans3 = ans4 = ( int ) 1e9 ; if ( mat [ n - 1 , m ] == 0 ) { if ( ! vis [ n - 1 , m ] ) ans1 = 1 + findMinSteps ( mat , n - 1 , m , dp , vis ) ; } if ( mat [ n , m + 1 ] == 0 ) { if ( ! vis [ n , m + 1 ] ) ans2 = 1 + findMinSteps ( mat , n , m + 1 , dp , vis ) ; } if ( mat [ n , m - 1 ] == 0 ) { if ( ! vis [ n , m - 1 ] ) ans3 = 1 + findMinSteps ( mat , n , m - 1 , dp , vis ) ; } if ( mat [ n + 1 , m ] == 0 ) { if ( ! vis [ n + 1 , m ] ) ans4 = 1 + findMinSteps ( mat , n + 1 , m , dp , vis ) ; } dp [ n , m ] = Math . Min ( ans1 , Math . Min ( ans2 , Math . Min ( ans3 , ans4 ) ) ) ; return dp [ n , m ] ; } static int minimumSteps ( int [ , ] mat , int n , int m ) { int twox = - 1 ; int twoy = - 1 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( mat [ i , j ] == 2 ) { twox = i ; twoy = j ; break ; } } if ( twox != - 1 ) break ; } int [ , ] dp = new int [ r , r ] ; for ( int j = 0 ; j < r ; j ++ ) for ( int i = 0 ; i < r ; i ++ ) dp [ j , i ] = - 1 ; bool [ , ] vis = new bool [ r , r ] ; for ( int j = 0 ; j < r ; j ++ ) for ( int i = 0 ; i < r ; i ++ ) vis [ j , i ] = false ; int res = findMinSteps ( mat , twox , twoy , dp , vis ) ; if ( res >= 1e9 ) return - 1 ; else return res ; } public static void Main ( ) { int [ , ] mat = { { 1 , 1 , 1 , 0 , 1 } , { 1 , 0 , 2 , 0 , 1 } , { 0 , 0 , 1 , 0 , 1 } , { 1 , 0 , 1 , 1 , 0 } , } ; Console . WriteLine ( minimumSteps ( mat , r , c ) ) ; } }