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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define r  4 NEW_LINE #define col  5 NEW_LINE int findMinSteps ( int mat [ r ] [ col ] , int n , int m , int dp [ r ] [ col ] , bool vis [ r ] [ col ] ) { if ( n == 0 || m == 0 || n == ( r - 1 ) || m == ( col - 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 = 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 ] = min ( ans1 , min ( ans2 , min ( ans3 , ans4 ) ) ) ; return dp [ n ] [ m ] ; } int minimumSteps ( int mat [ r ] [ col ] , 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 [ r ] [ col ] ; memset ( dp , -1 , sizeof dp ) ; bool vis [ r ] [ col ] ; memset ( vis , false , sizeof vis ) ; int res = findMinSteps ( mat , twox , twoy , dp , vis ) ; if ( res >= 1e9 ) return -1 ; else return res ; } int main ( ) { int mat [ r ] [ col ] = { { 1 , 1 , 1 , 0 , 1 } , { 1 , 0 , 2 , 0 , 1 } , { 0 , 0 , 1 , 0 , 1 } , { 1 , 0 , 1 , 1 , 0 } } ; cout << minimumSteps ( mat , r , col ) ; }