Paths with maximum number of ' a ' from ( 1 , 1 ) to ( X , Y ) vertically or horizontally | Java program to find paths with maximum number of ' a ' from ( 1 , 1 ) to ( X , Y ) vertically or horizontally ; Function to answer queries ; Iterate till query ; Decrease to get 0 - based indexing ; Print answer ; Function that pre - computes the dp array ; Check fo the first character ; Iterate in row and columns ; If not first row or not first column ; Not first row ; Not first column ; If it is not ' a ' then increase by 1 ; Driver code ; character N X N array ; queries ; number of queries ; function call to pre - compute ; function call to answer every query
class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int n = 3 ; static int [ ] [ ] dp = new int [ n ] [ n ] ; static void answerQueries ( pair queries [ ] , int q ) { for ( int i = 0 ; i < q ; i ++ ) { int x = queries [ i ] . first ; x -- ; int y = queries [ i ] . second ; y -- ; System . out . println ( dp [ x ] [ y ] ) ; } } static void pre_compute ( char a [ ] [ ] ) { if ( a [ 0 ] [ 0 ] == ' a ' ) dp [ 0 ] [ 0 ] = 0 ; else dp [ 0 ] [ 0 ] = 1 ; for ( int row = 0 ; row < n ; row ++ ) { for ( int col = 0 ; col < n ; col ++ ) { if ( row != 0 col != 0 ) dp [ row ] [ col ] = Integer . MAX_VALUE ; if ( row != 0 ) { dp [ row ] [ col ] = Math . min ( dp [ row ] [ col ] , dp [ row - 1 ] [ col ] ) ; } if ( col != 0 ) { dp [ row ] [ col ] = Math . min ( dp [ row ] [ col ] , dp [ row ] [ col - 1 ] ) ; } if ( a [ row ] [ col ] != ' a ' && ( row != 0 col != 0 ) ) dp [ row ] [ col ] += 1 ; } } } public static void main ( String [ ] args ) { char a [ ] [ ] = { { ' a ' , ' b ' , ' a ' } , { ' a ' , ' c ' , ' d ' } , { ' b ' , ' a ' , ' b ' } } ; pair queries [ ] = { new pair ( 1 , 3 ) , new pair ( 3 , 3 ) } ; int q = 2 ; pre_compute ( a ) ; answerQueries ( queries , q ) ; } }