Paths with maximum number of ' a ' from ( 1 , 1 ) to ( X , Y ) vertically or horizontally | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int n = 3 ; int dp [ n ] [ n ] ; void answerQueries ( pair < int , int > queries [ ] , int q ) { for ( int i = 0 ; i < q ; i ++ ) { int x = queries [ i ] . first ; x -- ; int y = queries [ i ] . second ; y -- ; cout << dp [ x ] [ y ] << endl ; } } void pre_compute ( char a [ ] [ n ] ) { 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 ] = INT_MAX ; if ( row != 0 ) { dp [ row ] [ col ] = min ( dp [ row ] [ col ] , dp [ row - 1 ] [ col ] ) ; } if ( col != 0 ) { dp [ row ] [ col ] = min ( dp [ row ] [ col ] , dp [ row ] [ col - 1 ] ) ; } if ( a [ row ] [ col ] != ' a ' && ( row != 0 col != 0 ) ) dp [ row ] [ col ] += 1 ; } } } int main ( ) { char a [ ] [ 3 ] = { { ' a ' , ' b ' , ' a ' } , { ' a ' , ' c ' , ' d ' } , { ' b ' , ' a ' , ' b ' } } ; pair < int , int > queries [ ] = { { 1 , 3 } , { 3 , 3 } } ; int q = 2 ; pre_compute ( a ) ; answerQueries ( queries , q ) ; }