Dada una array de tamaño NXM que consta de ‘#’, ‘.’ y ‘*’. ‘#’ significa ruta bloqueada, ‘.’ significa camino transitable y ‘*’ significa puntos que debe acumular. Ahora considere que está en la parte superior izquierda de la array. Tienes que llegar a la parte inferior derecha de la array y volver a la parte superior izquierda. Cuando te mueves de arriba a la izquierda hacia abajo a la derecha, puedes caminar hacia la derecha o hacia abajo. Y cuando mueve la parte inferior derecha a la parte superior izquierda, puede caminar hacia la izquierda o hacia arriba. La tarea es encontrar el máximo de puntos que puede obtener durante todo su viaje. Los puntos una vez obtenidos se convertirán en ‘.’ es decir, camino transitable.
Ejemplos:
Input : N = 3, M = 4 **** .##. .##. **** Output : 8 Input : N = 9, M = 7 *........ .....**#. ..**...#* ..####*#. .*.#*.*#. ...#**... *........ Output : 7
Si considera dos caminos, uno desde (0, 0) a (N – 1, M – 1) y otro desde (N – 1, M – 1) a (0, 0) y recopila el máximo * en cada camino. Podrías terminar con una respuesta incorrecta. Si agrega la respuesta de ambos caminos de forma independiente, estará calculando los puntos de intersección una vez más mientras retrocede. Esencialmente, terminar con el mismo camino. Incluso si mantiene una array visitada, marcando cada * en la primera ruta, aún no obtendrá la respuesta correcta.
Considere el siguiente ejemplo:
Si consideramos como dos caminos independientes, entonces
el total * recolectado es 7.
Mientras que el máximo de puntos recolectados puede ser 8 siguiendo las rutas.
Hay 4 * en cada camino. Por lo tanto, total = 8.
Así vemos que la solución óptima no es la suma de las soluciones óptimas de ambos caminos de forma independiente. La respuesta óptima para uno no asegura una respuesta óptima.
Entonces, tendremos que calcular ambos caminos simultáneamente. Esto es necesario porque la respuesta para la ruta 2 depende de la ruta elegida por la ruta 1. Se pueden realizar cálculos simultáneos considerando dos rutas desde (0, 0) a (N-1, M-1) y tomando cuatro decisiones en cada posición. (dos para cada uno).
Entonces, en lugar de que dos viajen por un camino de arriba a la izquierda a abajo a la derecha y otro de abajo a la derecha a arriba a la izquierda, viajaremos dos caminos de (0, 0) a (N-1, M-1) simultáneamente, así que en cada paso, damos un paso para ambos caminos. Entonces nuestro estado consistirá en (x1, y1, x2, y2) donde (x1, y1) es la posición del primer camino y (x2, y2) es la posición del segundo turista en la cuadrícula.
Puntos a notar:
- En cada paso, cualquiera de los pasos puede moverse hacia la derecha o hacia abajo, por lo que tenemos 4 opciones de movimiento (2 opciones para cada camino).
- Si ambas rutas están en la misma celda (x1 == x2 e y1 == y2), entonces podemos agregar solo 1 al resultado si esa celda tiene *.
- Podemos reducir la complejidad reduciendo la dimensión de estado de 4 a 3. Si conocemos la posición del primer camino (x1, y1) la coordenada x del segundo camino x2, entonces debemos tener x1 + y1 = x2 + y2 ya que ambos caminos cubrir la misma distancia en la misma cantidad de tiempo. Entonces y2 = x1 + y1 – x2 y nuestro estado depende solo de (x1, y1, x2).
A continuación se muestra la implementación de este enfoque:
C++
// CPP program to find maximum points that can
// be collected in a journey from top to bottom
// and then back from bottom to top,
#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
// Calculating the points at a (row1, col1) &&
// (row2, col2) from path1 && path2
int cost(char grid[][M], int row1, int col1,
int row2, int col2)
{
// If both path is at same cell
if (row1 == row2 && col1 == col2) {
// If the cell contain *, return 1
if (grid[row1][col1] == '*')
return 1;
// else return 0.
return 0;
}
int ans = 0;
// If path 1 contain *, add to answer.
if (grid[row1][col1] == '*')
ans++;
// If path contain *, add to answer.
if (grid[row2][col2] == '*')
ans++;
return ans;
}
// Calculate the maximum points that can be
// collected.
int solve(int n, int m, char grid[][M],
int dp[MAX][MAX][MAX], int row1,
int col1, int row2)
{
int col2 = (row1 + col1) - (row2);
// If both path reach the bottom right cell
if (row1 == n - 1 && col1 == m - 1 &&
row2 == n - 1 && col2 == m - 1)
return 0;
// If moving out of grid
if (row1 >= n || col1 >= m ||
row2 >= n || col2 >= m)
return -1 * inf;
// If already calculated, return the value
if (dp[row1][col1][row2] != -1)
return dp[row1][col1][row2];
// Variable for 4 options.
int ch1 = -1 * inf, ch2 = -1 * inf;
int ch3 = -1 * inf, ch4 = -1 * inf;
// If path 1 is moving right and path 2
// is moving down.
if (col1 + 1 < m && row2 + 1 < n && grid[row1][col1 + 1] != '#' &&
grid[row2 + 1][col2] != '#')
ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) +
solve(n, m, grid, dp, row1, col1 + 1, row2 + 1);
// If path 1 is moving right and path 2 is moving
// right.
if (col2 + 1 < m && col1 + 1 < m && grid[row1][col1 + 1] != '#' &&
grid[row2][col2 + 1] != '#')
ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) +
solve(n, m, grid, dp, row1, col1 + 1, row2);
// If path 1 is moving down and path 2 is moving right.
if (col2 + 1 < m && row1 + 1 < n && grid[row1 + 1][col1] != '#' &&
grid[row2][col2 + 1] != '#')
ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) +
solve(n, m, grid, dp, row1 + 1, col1, row2);
// If path 1 is moving down and path 2 is moving down.
if (row1 + 1 < n && row2 + 1 < n && grid[row1 + 1][col1] != '#' &&
grid[row2 + 1][col2] != '#')
ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) +
solve(n, m, grid, dp, row1 + 1, col1, row2 + 1);
// Returning the maximum of 4 options.
return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}
// Wrapper Function
int wrapper(int n, int m, char grid[N][M])
{
int ans = 0;
int dp[MAX][MAX][MAX];
memset(dp, -1, sizeof dp);
// If last bottom right cell is blocked
if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
ans = -1 * inf;
// If top left cell contain *
if (grid[0][0] == '*')
ans++;
grid[0][0] = '.';
// If bottom right cell contain *
if (grid[n - 1][m - 1] == '*')
ans++;
grid[n - 1][m - 1] = '.';
ans += solve(n, m, grid, dp, 0, 0, 0);
return max(ans, 0);
}
// Driven Program
int main()
{
int n = 5, m = 5;
char grid[N][M] = {
{ '.', '*', '.', '*', '.' },
{ '*', '#', '#', '#', '.' },
{ '*', '.', '*', '.', '*' },
{ '.', '#', '#', '#', '*' },
{ '.', '*', '.', '*', '.' }
};
cout << wrapper(n, m, grid) << endl;
return 0;
}
Java
// Java program to find maximum points that can
// be collected in a journey from top to bottom
// and then back from bottom to top,
import java.io.*;
class GFG {
static int MAX = 5;
static int N = 5;
static int M = 5;
static int inf = 100000;
// Calculating the points at a (row1, col1) &&
// (row2, col2) from path1 && path2
public static int cost(char grid[][], int row1,
int col1, int row2, int col2)
{
// If both path is at same cell
if (row1 == row2 && col1 == col2) {
// If the cell contain *, return 1
if (grid[row1][col1] == '*')
return 1;
// else return 0.
return 0;
}
int ans = 0;
// If path 1 contain *, add to answer.
if (grid[row1][col1] == '*')
ans++;
// If path contain *, add to answer.
if (grid[row2][col2] == '*')
ans++;
return ans;
}
// Calculate the maximum points that can be
// collected.
public static int solve(int n, int m, char grid[][],
int dp[][][], int row1,
int col1, int row2)
{
int col2 = (row1 + col1) - (row2);
// If both path reach the bottom right cell
if (row1 == n - 1 && col1 == m - 1 && row2 == n - 1
&& col2 == m - 1)
return 0;
// If moving out of grid
if (row1 >= n || col1 >= m || row2 >= n
|| col2 >= m)
return -1 * inf;
// If already calculated, return the value
if (dp[row1][col1][row2] != -1)
return dp[row1][col1][row2];
// Variable for 4 options.
int ch1 = -1 * inf, ch2 = -1 * inf;
int ch3 = -1 * inf, ch4 = -1 * inf;
// If path 1 is moving right and path 2
// is moving down.
if (col1 + 1 < m && row2 + 1 < n
&& grid[row1][col1 + 1] != '#'
&& grid[row2 + 1][col2] != '#')
ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2)
+ solve(n, m, grid, dp, row1, col1 + 1,
row2 + 1);
// If path 1 is moving right and path 2 is moving
// right.
if (col2 + 1 < m && col1 + 1 < m
&& grid[row1][col1 + 1] != '#'
&& grid[row2][col2 + 1] != '#')
ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1)
+ solve(n, m, grid, dp, row1, col1 + 1,
row2);
// If path 1 is moving down and path 2 is moving
// right.
if (col2 + 1 < m && row1 + 1 < n
&& grid[row1 + 1][col1] != '#'
&& grid[row2][col2 + 1] != '#')
ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1)
+ solve(n, m, grid, dp, row1 + 1, col1,
row2);
// If path 1 is moving down and path 2 is moving
// down.
if (row1 + 1 < n && row2 + 1 < n
&& grid[row1 + 1][col1] != '#'
&& grid[row2 + 1][col2] != '#')
ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2)
+ solve(n, m, grid, dp, row1 + 1, col1,
row2 + 1);
// Returning the maximum of 4 options.
return dp[row1][col1][row2] = Math.max(
ch1, Math.max(ch2, Math.max(ch3, ch4)));
}
// Wrapper Function
public static int wrapper(int n, int m, char grid[][])
{
int ans = 0;
int dp[][][] = new int[MAX][MAX][MAX];
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
for (int k = 0; k < MAX; k++)
dp[i][j][k] = -1;
// If last bottom right cell is blocked
if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
ans = -1 * inf;
// If top left cell contain *
if (grid[0][0] == '*')
ans++;
grid[0][0] = '.';
// If bottom right cell contain *
if (grid[n - 1][m - 1] == '*')
ans++;
grid[n - 1][m - 1] = '.';
ans += solve(n, m, grid, dp, 0, 0, 0);
return Math.max(ans, 0);
}
// Driver Code
public static void main(String[] args)
{
int n = 5, m = 5;
char grid[][] = { { '.', '*', '.', '*', '.' },
{ '*', '#', '#', '#', '.' },
{ '*', '.', '*', '.', '*' },
{ '.', '#', '#', '#', '*' },
{ '.', '*', '.', '*', '.' } };
System.out.println(wrapper(n, m, grid));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python3 program to find maximum points # that can be collected in a journey from # top to bottom and then back from bottom to top, MAX = 5 N = 5 M = 5 inf = 100000 # Calculating the points at a (row1, col1) and # (row2, col2) from path1 and path2 def cost(grid, row1, col1, row2, col2): # If both path is at same cell if (row1 == row2 and col1 == col2): # If the cell contain *, return 1 if (grid[row1][col1] == '*'): return 1 # else return 0. return 0 ans = 0 # If path 1 contain *, add to answer. if (grid[row1][col1] == '*'): ans += 1 # If path contain *, add to answer. if (grid[row2][col2] == '*'): ans += 1 return ans # Calculate the maximum points that can be # collected. def solve(n, m, grid, dp, row1, col1, row2): col2 = (row1 + col1) - (row2) # If both path reach the bottom right cell if (row1 == n - 1 and col1 == m - 1 and row2 == n - 1 and col2 == m - 1): return 0 # If moving out of grid if (row1 >= n or col1 >= m or row2 >= n or col2 >= m): return -1 * inf # If already calculated, return the value if (dp[row1][col1][row2] != -1): return dp[row1][col1][row2] # Variable for 4 options. ch1 = -1 * inf ch2 = -1 * inf ch3 = -1 * inf ch4 = -1 * inf # If path 1 is moving right and path 2 # is moving down. if (col1 + 1 < m and row2 + 1 < n and grid[row1][col1 + 1] != '#' and grid[row2 + 1][col2] != '#'): ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) + \ solve(n, m, grid, dp, row1, col1 + 1, row2 + 1) # If path 1 is moving right and path 2 # is moving right. if (col1 + 1 < m and col2 + 1 < m and grid[row1][col1 + 1] != '#' and grid[row2][col2 + 1] != '#'): ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) + \ solve(n, m, grid, dp, row1, col1 + 1, row2) # If path 1 is moving down and path 2 # is moving right. if (row1 + 1 < n and col2 + 1 < m and grid[row1 + 1][col1] != '#' and grid[row2][col2 + 1] != '#'): ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) + \ solve(n, m, grid, dp, row1 + 1, col1, row2) # If path 1 is moving down and path 2 is moving down. if (row1 + 1 < n and row2 + 1 < n and grid[row1 + 1][col1] != '#' and grid[row2 + 1][col2] != '#'): ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) + \ solve(n, m, grid, dp, row1 + 1, col1, row2 + 1) # Returning the maximum of 4 options. dp[row1][col1][row2] = max(ch1, ch2, ch3, ch4) return dp[row1][col1][row2] # Wrapper Function def wrapper(n, m, grid): ans = 0 dp = [[[-1] * MAX for i in range(MAX)] for j in range(MAX)] # If last bottom right cell is blocked if (grid[n - 1][m - 1] == '#' or grid[0][0] == '#'): ans = -1 * inf # If top left cell contain * if (grid[0][0] == '*'): ans += 1 grid[0][0] = '.' # If bottom right cell contain * if (grid[n - 1][m - 1] == '*'): ans += 1 grid[n - 1][m - 1] = '.' ans += solve(n, m, grid, dp, 0, 0, 0) return max(ans, 0) # Driver Code if __name__ == '__main__': n = 5 m = 5 grid = [[ '.', '*', '.', '*', '.' ], [ '*', '#', '#', '#', '.' ], [ '*', '.', '*', '.', '*' ], [ '.', '#', '#', '#', '*' ], [ '.', '*', '.', '*', '.' ]] print(wrapper(n, m, grid)) # This code is contributed by ashutosh450
Javascript
<script>
// JavaScript program to find maximum points
// that can be collected in a journey from
// top to bottom && then back from bottom to top,
const MAX = 5
const N = 5
const M = 5
const inf = 100000
// Calculating the points at a (row1, col1) &&
// (row2, col2) from path1 && path2
function cost(grid, row1, col1, row2, col2){
// If both path is at same cell
if (row1 == row2 && col1 == col2){
// If the cell contain *, return 1
if (grid[row1][col1] == '*'){
return 1
}
// else return 0.
return 0
}
let ans = 0
// If path 1 contain *, add to answer.
if (grid[row1][col1] == '*')
ans += 1
// If path contain *, add to answer.
if (grid[row2][col2] == '*')
ans += 1
return ans
}
// Calculate the maximum points that can be
// collected.
function solve(n, m, grid, dp, row1, col1, row2){
let col2 = (row1 + col1) - (row2)
// If both path reach the bottom right cell
if (row1 == n - 1 && col1 == m - 1 &&
row2 == n - 1 && col2 == m - 1)
return 0
// If moving out of grid
if (row1 >= n || col1 >= m ||
row2 >= n || col2 >= m)
return -1 * inf
// If already calculated, return the value
if (dp[row1][col1][row2] != -1)
return dp[row1][col1][row2]
// Variable for 4 options.
let ch1 = -1 * inf
let ch2 = -1 * inf
let ch3 = -1 * inf
let ch4 = -1 * inf
// If path 1 is moving right && path 2
// is moving down.
if (col1 + 1 < m && row2 + 1 < n &&
grid[row1][col1 + 1] != '#' &&
grid[row2 + 1][col2] != '#'){
ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) +
solve(n, m, grid, dp, row1, col1 + 1, row2 + 1)
}
// If path 1 is moving right && path 2
// is moving right.
if (col1 + 1 < m && col2 + 1 < m &&
grid[row1][col1 + 1] != '#' &&
grid[row2][col2 + 1] != '#')
ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) +
solve(n, m, grid, dp, row1, col1 + 1, row2)
// If path 1 is moving down && path 2
// is moving right.
if (row1 + 1 < n && col2 + 1 < m &&
grid[row1 + 1][col1] != '#' &&
grid[row2][col2 + 1] != '#')
ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) +
solve(n, m, grid, dp, row1 + 1, col1, row2)
// If path 1 is moving down && path 2 is moving down.
if (row1 + 1 < n && row2 + 1 < n &&
grid[row1 + 1][col1] != '#' &&
grid[row2 + 1][col2] != '#')
ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) +
solve(n, m, grid, dp, row1 + 1, col1, row2 + 1)
// Returning the maximum of 4 options.
dp[row1][col1][row2] = Math.max(ch1, ch2, ch3, ch4)
return dp[row1][col1][row2]
}
// Wrapper Function
function wrapper(n, m, grid){
let ans = 0
let dp = new Array(MAX)
for(let i = 0; i < MAX; i++)
{
dp[i] = new Array(MAX);
for(let j = 0; j < MAX; j++)
{
dp[i][j] = new Array(MAX).fill(-1);
}
}
// If last bottom right cell is blocked
if (grid[n - 1][m - 1] == '#' ||
grid[0][0] == '#')
ans = -1 * inf
// If top left cell contain *
if (grid[0][0] == '*')
ans += 1
grid[0][0] = '.'
// If bottom right cell contain *
if (grid[n - 1][m - 1] == '*')
ans += 1
grid[n - 1][m - 1] = '.'
ans += solve(n, m, grid, dp, 0, 0, 0)
return Math.max(ans, 0)
}
// Driver Code
let n = 5
let m = 5
let grid = [[ '.', '*', '.', '*', '.' ],
[ '*', '#', '#', '#', '.' ],
[ '*', '.', '*', '.', '*' ],
[ '.', '#', '#', '#', '*' ],
[ '.', '*', '.', '*', '.' ]]
document.write(wrapper(n, m, grid))
// This code is contributed by shinjanpatra
</script>
Producción
8
Complejidad de tiempo: O(N^3)
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA