Paths with maximum number of ' a ' from ( 1 , 1 ) to ( X , Y ) vertically or horizontally | Python3 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 for 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
n = 3 NEW_LINE dp = [ [ 0 for i in range ( n ) ] for j in range ( n ) ] NEW_LINE def answerQueries ( queries , q ) : NEW_LINE INDENT for i in range ( q ) : NEW_LINE INDENT x = queries [ i ] [ 0 ] NEW_LINE x -= 1 NEW_LINE y = queries [ i ] [ 1 ] NEW_LINE y -= 1 NEW_LINE print ( dp [ x ] [ y ] ) NEW_LINE DEDENT DEDENT def pre_compute ( a ) : NEW_LINE INDENT if a [ 0 ] [ 0 ] == ' a ' : NEW_LINE INDENT dp [ 0 ] [ 0 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 0 ] [ 0 ] = 1 NEW_LINE DEDENT for row in range ( n ) : NEW_LINE INDENT for col in range ( n ) : NEW_LINE INDENT if ( row != 0 or col != 0 ) : NEW_LINE INDENT dp [ row ] [ col ] = 9999 NEW_LINE DEDENT if ( row != 0 ) : NEW_LINE INDENT dp [ row ] [ col ] = min ( dp [ row ] [ col ] , dp [ row - 1 ] [ col ] ) NEW_LINE DEDENT if ( col != 0 ) : NEW_LINE INDENT dp [ row ] [ col ] = min ( dp [ row ] [ col ] , dp [ row ] [ col - 1 ] ) NEW_LINE DEDENT if ( a [ row ] [ col ] != ' a ' and ( row != 0 or col != 0 ) ) : NEW_LINE INDENT dp [ row ] [ col ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ ( ' a ' , ' b ' , ' a ' ) , ( ' a ' , ' c ' , ' d ' ) , ( ' b ' , ' a ' , ' b ' ) ] NEW_LINE queries = [ ( 1 , 3 ) , ( 3 , 3 ) ] NEW_LINE q = 2 NEW_LINE pre_compute ( a ) NEW_LINE answerQueries ( queries , q ) NEW_LINE DEDENT