Paths with maximum number of ' a ' from ( 1 , 1 ) to ( X , Y ) vertically or horizontally | Javascript 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 ; character N X N array ; queries ; number of queries ; function call to pre - compute ; function call to answer every query
class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } let n = 3 ; let dp = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( n ) ; for ( let j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = 0 ; } } function answerQueries ( queries , q ) { for ( let i = 0 ; i < q ; i ++ ) { let x = queries [ i ] . first ; x -- ; let y = queries [ i ] . second ; y -- ; document . write ( dp [ x ] [ y ] + " " ) ; } } function pre_compute ( a ) { if ( a [ 0 ] [ 0 ] == ' ' ) dp [ 0 ] [ 0 ] = 0 ; else dp [ 0 ] [ 0 ] = 1 ; for ( let row = 0 ; row < n ; row ++ ) { for ( let col = 0 ; col < n ; col ++ ) { if ( row != 0 col != 0 ) dp [ row ] [ col ] = Number . 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 ] != ' ' && ( row != 0 col != 0 ) ) dp [ row ] [ col ] += 1 ; } } } let a = [ [ ' ' , ' ' , ' ' ] , [ ' ' , ' ' , ' ' ] , [ ' ' , ' ' , ' ' ] ] ; let queries = [ new pair ( 1 , 3 ) , new pair ( 3 , 3 ) ] ; let q = 2 ; pre_compute ( a ) ; answerQueries ( queries , q ) ;