Check if a path exists from a given cell to any boundary element of the Matrix with sum of elements not exceeding K | Python3 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
import sys NEW_LINE INT_MAX = sys . maxsize NEW_LINE def isValid ( board , i , j , K ) : NEW_LINE INDENT if ( board [ i ] [ j ] <= K ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def findPath ( board , X , Y , M , N , K ) : NEW_LINE INDENT if ( X < 0 or X == M or Y < 0 or Y == N ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( isValid ( board , X , Y , K ) ) : NEW_LINE INDENT board_XY = board [ X ] [ Y ] NEW_LINE board [ X ] [ Y ] = INT_MAX NEW_LINE if ( findPath ( board , X + 1 , Y , M , N , K - board_XY ) or findPath ( board , X - 1 , Y , M , N , K - board_XY ) or findPath ( board , X , Y + 1 , M , N , K - board_XY ) or findPath ( board , X , Y - 1 , M , N , K - board_XY ) ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT board [ X ] [ Y ] = board_XY NEW_LINE DEDENT return False NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT 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 ] ] NEW_LINE K = 17 NEW_LINE M = len ( grid ) NEW_LINE N = len ( grid [ 0 ] ) NEW_LINE X = 2 NEW_LINE Y = 3 NEW_LINE if ( findPath ( grid , X , Y , M , N , K ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT