Dada una array NXN que consta de caracteres. También se dan consultas Q, donde cada consulta contiene una coordenada (X, Y). Para cada consulta, busque todas las rutas de (1, 1) a (X, Y) moviéndose vertical u horizontalmente y tome la ruta que tenga el número máximo de . La tarea es imprimir el número de caracteres que no son ‘a’ a lo largo de esa ruta.
Ejemplos :
Input: mat[][] = {{'a', 'b', 'a'}, {'a', 'c', 'd'}, {'b', 'a', 'b'}} Queries: X = 1, Y = 3 X = 3, Y = 3 Output: 1st query: 1 2nd query: 2 Query-1: There is only one path from (1, 1) to (1, 3) i.e., "aba" and the number of characters which are not 'a' is 1. Query-2: The path which has the maximum number of 'a' in it is "aabab", hence non 'a' characters are 2.
El problema es una variante del problema Dp de ruta de costo mínimo . Necesitamos calcular previamente la array DP[][] y luego la respuesta será DP[X][Y], por lo tanto, todas las consultas se pueden responder en O(1). Si el carácter de la posición del índice (1, 1) no es ‘a’, aumente el valor de dp[1][1] en 1. Luego simplemente itere para filas y columnas, y haga un DP de costo mínimo considerando ‘a ‘ como 1 y el carácter que no es ‘a’ como 0. Dado que la array DP[][] almacena la ruta de costo mínimo desde (1, 1) a cualquier índice (i, j), por lo tanto, la consulta se puede responder en O(1 ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find paths with maximum number // of 'a' from (1, 1) to (X, Y) vertically // or horizontally #include <bits/stdc++.h> using namespace std; const int n = 3; int dp[n][n]; // Function to answer queries void answerQueries(pair<int, int> queries[], int q) { // Iterate till query for (int i = 0; i < q; i++) { // Decrease to get 0-based indexing int x = queries[i].first; x--; int y = queries[i].second; y--; // Print answer cout << dp[x][y] << endl; } } // Function that pre-computes the dp array void pre_compute(char a[][n]) { // Check for the first character if (a[0][0] == 'a') dp[0][0] = 0; else dp[0][0] = 1; // Iterate in row and columns for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { // If not first row or not first column if (row != 0 || col != 0) dp[row][col] = INT_MAX; // Not first row if (row != 0) { dp[row][col] = min(dp[row][col], dp[row - 1][col]); } // Not first column if (col != 0) { dp[row][col] = min(dp[row][col], dp[row][col - 1]); } // If it is not 'a' then increase by 1 if (a[row][col] != 'a' && (row != 0 || col != 0)) dp[row][col] += 1; } } } // Driver code int main() { // character N X N array char a[][3] = { { 'a', 'b', 'a' }, { 'a', 'c', 'd' }, { 'b', 'a', 'b' } }; // queries pair<int, int> queries[] = { { 1, 3 }, { 3, 3 } }; // number of queries int q = 2; // function call to pre-compute pre_compute(a); // function call to answer every query answerQueries(queries, q); }
Java
// Java program to find paths with maximum number // of 'a' from (1, 1) to (X, Y) vertically // or horizontally 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]; // Function to answer queries static void answerQueries(pair queries[], int q) { // Iterate till query for (int i = 0; i < q; i++) { // Decrease to get 0-based indexing int x = queries[i].first; x--; int y = queries[i].second; y--; // Print answer System.out.println(dp[x][y]); } } // Function that pre-computes the dp array static void pre_compute(char a[][]) { // Check for the first character if (a[0][0] == 'a') dp[0][0] = 0; else dp[0][0] = 1; // Iterate in row and columns for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { // If not first row or not first column if (row != 0 || col != 0) dp[row][col] = Integer.MAX_VALUE; // Not first row if (row != 0) { dp[row][col] = Math.min(dp[row][col], dp[row - 1][col]); } // Not first column if (col != 0) { dp[row][col] = Math.min(dp[row][col], dp[row][col - 1]); } // If it is not 'a' then increase by 1 if (a[row][col] != 'a' && (row != 0 || col != 0)) dp[row][col] += 1; } } } // Driver code public static void main(String[] args) { // character N X N array char a[][] = {{ 'a', 'b', 'a' }, { 'a', 'c', 'd' }, { 'b', 'a', 'b' }}; // queries pair queries[] = { new pair( 1, 3 ), new pair(3, 3 ) }; // number of queries int q = 2; // function call to pre-compute pre_compute(a); // function call to answer every query answerQueries(queries, q); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to find paths with maximum number # of 'a' from (1, 1) to (X, Y) vertically # or horizontally n = 3 dp = [[0 for i in range(n)] for j in range(n)] # Function to answer queries def answerQueries(queries, q): # Iterate till query for i in range(q): # Decrease to get 0-based indexing x = queries[i][0] x -= 1 y = queries[i][1] y -= 1 # Print answer print(dp[x][y]) # Function that pre-computes the dp array def pre_compute(a): # Check for the first character if a[0][0] == 'a': dp[0][0] = 0 else: dp[0][0] = 1 # Iterate in row and columns for row in range(n): for col in range(n): # If not first row or not first column if (row != 0 or col != 0): dp[row][col] = 9999 # Not first row if (row != 0): dp[row][col] = min(dp[row][col], dp[row - 1][col]) # Not first column if (col != 0): dp[row][col] = min(dp[row][col], dp[row][col - 1]) # If it is not 'a' then increase by 1 if (a[row][col] != 'a' and (row != 0 or col != 0)): dp[row][col] += 1 # Driver code if __name__ == '__main__': # Character N X N array a = [ ('a', 'b', 'a'), ('a', 'c', 'd'), ('b', 'a', 'b') ] # Queries queries = [ (1, 3), (3, 3) ] # Number of queries q = 2 # Function call to pre-compute pre_compute(a) # function call to answer every query answerQueries(queries, q) # This code is contributed by kirtishsurangalikar
C#
// C# program to find paths with maximum number // of 'a' from (1, 1) to (X, Y) vertically // or horizontally using System; class GFG { class pair { public 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]; // Function to answer queries static void answerQueries(pair []queries, int q) { // Iterate till query for (int i = 0; i < q; i++) { // Decrease to get 0-based indexing int x = queries[i].first; x--; int y = queries[i].second; y--; // Print answer Console.WriteLine(dp[x, y]); } } // Function that pre-computes the dp array static void pre_compute(char [,]a) { // Check for the first character if (a[0, 0] == 'a') dp[0, 0] = 0; else dp[0, 0] = 1; // Iterate in row and columns for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { // If not first row or not first column if (row != 0 || col != 0) dp[row, col] = int.MaxValue; // Not first row if (row != 0) { dp[row, col] = Math.Min(dp[row, col], dp[row - 1, col]); } // Not first column if (col != 0) { dp[row, col] = Math.Min(dp[row, col], dp[row, col - 1]); } // If it is not 'a' then increase by 1 if (a[row, col] != 'a' && (row != 0 || col != 0)) dp[row, col] += 1; } } } // Driver code public static void Main(String[] args) { // character N X N array char [,]a = {{ 'a', 'b', 'a' }, { 'a', 'c', 'd' }, { 'b', 'a', 'b' }}; // queries pair []queries = { new pair(1, 3), new pair(3, 3) }; // number of queries int q = 2; // function call to pre-compute pre_compute(a); // function call to answer every query answerQueries(queries, q); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript program to find paths with maximum number // of 'a' from (1, 1) to (X, Y) vertically // or horizontally 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 to answer queries function answerQueries(queries,q) { // Iterate till query for (let i = 0; i < q; i++) { // Decrease to get 0-based indexing let x = queries[i].first; x--; let y = queries[i].second; y--; // Print answer document.write(dp[x][y]+"<br>"); } } // Function that pre-computes the dp array function pre_compute(a) { // Check for the first character if (a[0][0] == 'a') dp[0][0] = 0; else dp[0][0] = 1; // Iterate in row and columns for (let row = 0; row < n; row++) { for (let col = 0; col < n; col++) { // If not first row or not first column if (row != 0 || col != 0) dp[row][col] = Number.MAX_VALUE; // Not first row if (row != 0) { dp[row][col] = Math.min(dp[row][col], dp[row - 1][col]); } // Not first column if (col != 0) { dp[row][col] = Math.min(dp[row][col], dp[row][col - 1]); } // If it is not 'a' then increase by 1 if (a[row][col] != 'a' && (row != 0 || col != 0)) dp[row][col] += 1; } } } // Driver code let a=[[ 'a', 'b', 'a' ], [ 'a', 'c', 'd' ], [ 'b', 'a', 'b' ]]; // queries let queries = [ new pair( 1, 3 ), new pair(3, 3 ) ]; // number of queries let q = 2; // function call to pre-compute pre_compute(a); // function call to answer every query answerQueries(queries, q); // This code is contributed by rag2127 </script>
1 2
Complejidad de tiempo : O(N 2 ) para precálculo y O(1) para cada consulta.
Espacio Auxiliar : O(N 2 )