Check if a path exists from a given cell to any boundary element of the Matrix with sum of elements not exceeding K | C ++ program for the above approach ; Function to check if it is valid to move to the given index or not ; Otherwise return false ; Function to check if there exists a path from the cell ( X , Y ) of the matrix to any boundary cell with sum of elements at most K or not ; Base Case ; If K >= board [ X ] [ Y ] ; Stores the current element ; Mark the current cell as visited ; Visit all the adjacent cells ; Mark the cell unvisited ; Return false ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isValid ( vector < vector < int > > & board , int i , int j , int K ) { if ( board [ i ] [ j ] <= K ) { return true ; } return false ; } bool findPath ( vector < vector < int > > & board , int X , int Y , int M , int N , int K ) { if ( X < 0 X == M Y < 0 Y == N ) { return true ; } if ( isValid ( board , X , Y , K ) ) { int board_XY = board [ X ] [ Y ] ; board [ X ] [ Y ] = INT_MAX ; if ( findPath ( board , X + 1 , Y , M , N , K - board_XY ) || findPath ( board , X - 1 , Y , M , N , K - board_XY ) || findPath ( board , X , Y + 1 , M , N , K - board_XY ) || findPath ( board , X , Y - 1 , M , N , K - board_XY ) ) { return true ; } board [ X ] [ Y ] = board_XY ; } return false ; } int main ( ) { vector < vector < int > > grid = { { 25 , 5 , 25 , 25 , 25 , 25 } , { 25 , 1 , 1 , 5 , 12 , 25 } , { 25 , 1 , 12 , 0 , 15 , 25 } , { 22 , 1 , 11 , 2 , 19 , 15 } , { 25 , 2 , 2 , 1 , 12 , 15 } , { 25 , 9 , 10 , 1 , 11 , 25 } , { 25 , 25 , 25 , 25 , 25 , 25 } } ; int K = 17 ; int M = grid . size ( ) ; int N = grid [ 0 ] . size ( ) ; int X = 2 , Y = 3 ; if ( findPath ( grid , X , Y , M , N , K ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }