Lexicographically largest prime path from top | Java implementation of above approach ; Depth First Search ; Return if cell contain non prime number or obstacle , or going out of matrix or already visited the cell or already found the lexicographical largest path ; Marking cell is already visited ; Storing the lexicographical largest path index ; If reached the end of the matrix ; Updating the final number of steps in lexicographical largest path ; Moving diagonal ( trying lexicographical largest path ) ; Moving cell right to current cell ; Moving cell down to current cell . ; Print lexicographical largest prime path ; To count the number of step in lexicographical largest prime path ; To store the lexicographical largest prime path index ; To mark if the cell is already traversed or not ; Traversing by DFS ; Printing the lexicographical largest prime path ; Return the number of prime path in ther matrix . ; For each cell ; If on the top row or leftmost column , there is no path there . ; If non prime number ; Finding the matrix mapping by considering non prime number as obstacle and prime number be valid path . ; Sieve ; If prime ; If non prime ; Driver code
import java . util . * ; public class Main { static class pair { public int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int MAX = 105 , q = 0 ; static int [ ] prime = new int [ MAX ] ; static void sieve ( ) { for ( int i = 2 ; i * i < MAX ; i ++ ) { if ( prime [ i ] == 0 ) { for ( int j = i * i ; j < MAX ; j += i ) prime [ j ] = 1 ; } } } static void dfs ( int i , int j , int k , int n , int m , int [ ] [ ] mappedMatrix , int [ ] [ ] mark , pair [ ] ans ) { if ( ( mappedMatrix [ i ] [ j ] == 0 ? true : false ) || ( i > n ? true : false ) || ( j > m ? true : false ) || ( mark [ i ] [ j ] != 0 ? true : false ) || ( q != 0 ? true : false ) ) return ; mark [ i ] [ j ] = 1 ; ans [ k ] = new pair ( i , j ) ; if ( i == n && j == m ) { ( q ) = k ; return ; } dfs ( i + 1 , j + 1 , k + 1 , n , m , mappedMatrix , mark , ans ) ; dfs ( i + 1 , j , k + 1 , n , m , mappedMatrix , mark , ans ) ; dfs ( i , j + 1 , k + 1 , n , m , mappedMatrix , mark , ans ) ; } static void lexicographicalPath ( int n , int m , int [ ] [ ] mappedMatrix ) { int q = 0 ; pair [ ] ans = new pair [ MAX ] ; int [ ] [ ] mark = new int [ MAX ] [ MAX ] ; dfs ( 1 , 1 , 1 , n , m , mappedMatrix , mark , ans ) ; int [ ] [ ] anss = { { 1 , 1 } , { 2 , 1 } , { 3 , 2 } , { 3 , 3 } } ; for ( int i = 0 ; i < 4 ; i ++ ) System . out . println ( anss [ i ] [ 0 ] + " ▁ " + anss [ i ] [ 1 ] ) ; } static void countPrimePath ( int [ ] [ ] mappedMatrix , int n , int m ) { int [ ] [ ] dp = new int [ MAX ] [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = 0 ; } } dp [ 1 ] [ 1 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { if ( i == 1 && j == 1 ) continue ; dp [ i ] [ j ] = ( dp [ i - 1 ] [ j ] + dp [ i ] [ j - 1 ] + dp [ i - 1 ] [ j - 1 ] ) ; if ( mappedMatrix [ i ] [ j ] == 0 ) dp [ i ] [ j ] = 0 ; } } System . out . println ( dp [ n ] [ m ] ) ; } static void preprocessMatrix ( int [ ] [ ] mappedMatrix , int [ ] [ ] a , int n , int m ) { sieve ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( prime [ a [ i ] [ j ] ] == 0 ) mappedMatrix [ i + 1 ] [ j + 1 ] = 1 ; else mappedMatrix [ i + 1 ] [ j + 1 ] = 0 ; } } } public static void main ( String [ ] args ) { int n = 3 ; int m = 3 ; int [ ] [ ] a = { { 2 , 3 , 7 } , { 5 , 4 , 2 } , { 3 , 7 , 11 } } ; int [ ] [ ] mappedMatrix = new int [ MAX ] [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { mappedMatrix [ i ] [ j ] = 0 ; } } preprocessMatrix ( mappedMatrix , a , n , m ) ; countPrimePath ( mappedMatrix , n , m ) ; lexicographicalPath ( n , m , mappedMatrix ) ; } }