Minimum initial vertices to traverse whole matrix with given conditions | Python3 program to find minimum initial vertices to reach whole matrix ; ( n , m ) is current source cell from which we need to do DFS . N and M are total no . of rows and columns . ; Marking the vertex as visited ; If below neighbor is valid and has value less than or equal to current cell 's value ; If right neighbor is valid and has value less than or equal to current cell 's value ; If above neighbor is valid and has value less than or equal to current cell 's value ; If left neighbor is valid and has value less than or equal to current cell 's value ; Storing the cell value and cell indices in a vector . ; Sorting the newly created array according to cell values ; Create a visited array for DFS and initialize it as false . ; Applying dfs for each vertex with highest value ; If the given vertex is not visited then include it in the set ; Driver code
MAX = 100 NEW_LINE def dfs ( n , m , visit , adj , N , M ) : NEW_LINE INDENT visit [ n ] [ m ] = 1 NEW_LINE if ( n + 1 < N and adj [ n ] [ m ] >= adj [ n + 1 ] [ m ] and not visit [ n + 1 ] [ m ] ) : NEW_LINE INDENT dfs ( n + 1 , m , visit , adj , N , M ) NEW_LINE DEDENT if ( m + 1 < M and adj [ n ] [ m ] >= adj [ n ] [ m + 1 ] and not visit [ n ] [ m + 1 ] ) : NEW_LINE INDENT dfs ( n , m + 1 , visit , adj , N , M ) NEW_LINE DEDENT if ( n - 1 >= 0 and adj [ n ] [ m ] >= adj [ n - 1 ] [ m ] and not visit [ n - 1 ] [ m ] ) : NEW_LINE INDENT dfs ( n - 1 , m , visit , adj , N , M ) NEW_LINE DEDENT if ( m - 1 >= 0 and adj [ n ] [ m ] >= adj [ n ] [ m - 1 ] and not visit [ n ] [ m - 1 ] ) : NEW_LINE INDENT dfs ( n , m - 1 , visit , adj , N , M ) NEW_LINE DEDENT DEDENT def printMinSources ( adj , N , M ) : NEW_LINE INDENT x = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT x . append ( [ adj [ i ] [ j ] , [ i , j ] ] ) NEW_LINE DEDENT DEDENT x . sort ( ) NEW_LINE visit = [ [ False for i in range ( MAX ) ] for i in range ( N ) ] NEW_LINE for i in range ( len ( x ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( not visit [ x [ i ] [ 1 ] [ 0 ] ] [ x [ i ] [ 1 ] [ 1 ] ] ) : NEW_LINE INDENT print ( ' { } ▁ { } ' . format ( x [ i ] [ 1 ] [ 0 ] , x [ i ] [ 1 ] [ 1 ] ) ) NEW_LINE dfs ( x [ i ] [ 1 ] [ 0 ] , x [ i ] [ 1 ] [ 1 ] , visit , adj , N , M ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE M = 2 NEW_LINE adj = [ [ 3 , 3 ] , [ 1 , 1 ] ] NEW_LINE printMinSources ( adj , N , M ) NEW_LINE DEDENT