Dada una cuadrícula bidimensional, cada celda de la cual contiene un costo entero que representa un costo para atravesar esa celda. La tarea es encontrar la ruta de costo máximo desde la esquina inferior izquierda hasta la esquina superior derecha.
Nota: use solo movimientos hacia arriba y hacia la derecha
Ejemplos:
Input : mat[][] = {{20, -10, 0},
{1, 5, 10},
{1, 2, 3}}
Output : 18
(2, 0) ==> (2, 1) ==> (1, 1) ==> (1, 2) ==> (0, 2)
cost for this path is (1+2+5+10+0) = 18
Input : mat[][] = {{1, -2, -3},
{1, 15, 10},
{1, -2, 3}}
Output : 24
Requisitos previos: ruta de costo mínimo con movimientos permitidos hacia la izquierda, derecha, abajo y hacia arriba
Enfoque: la idea es mantener una array separada para almacenar el costo máximo para todas las celdas que usan queue . Para cada celda, compruebe si el costo actual para llegar a esa celda es mayor que el costo anterior o no. Si el costo anterior es mínimo, actualice la celda con el costo actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum cost to reach
// top right corner from bottom left corner
#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 3
// To store matrix cell coordinates
struct Point
{
int x;
int y;
};
// Check whether given cell (row, col)
// is a valid cell or not.
bool isValid(Point p)
{
// Return true if row number and column number
// is in range
return (p.x >=0) && (p.y <COL);
}
// Function to find maximum cost to reach
// top right corner from bottom left corner
int find_max_cost(int mat[][COL])
{
int max_val[ROW][COL];
memset(max_val, 0, sizeof max_val);
max_val[ROW-1][0] = mat[ROW-1][0];
// Starting point
Point src = {ROW-1,0};
// Create a queue for traversal
queue<Point> q;
q.push(src); // Enqueue source cell
// Do a BFS starting from source cell
// on the allowed direction
while (!q.empty())
{
Point curr = q.front();
q.pop();
// Find up point
Point up = {curr.x-1, curr.y};
// if adjacent cell is valid, enqueue it.
if (isValid(up))
{
max_val[up.x][up.y] = max(max_val[up.x][up.y],
mat[up.x][up.y] + max_val[curr.x][curr.y]);
q.push(up);
}
// Find right point
Point right = {curr.x, curr.y+1};
if(isValid(right))
{
max_val[right.x][right.y] = max(max_val[right.x][right.y],
mat[right.x][right.y] + max_val[curr.x][curr.y]);
q.push(right);
}
}
// Return the required answer
return max_val[0][COL-1];
}
// Driver code
int main()
{
int mat[ROW][COL] = { {20, -10, 0},
{1, 5, 10},
{1, 2, 3},};
std::cout<<"Given matrix is "<<endl;
for(int i = 0 ; i<ROW;++i)
{
for(int j =0; j<COL; ++j)
std::cout<<mat[i][j]<<" ";
std::cout<<endl;
}
std::cout<<"Maximum cost is " << find_max_cost(mat);
return 0;
}
Java
// Java program to find maximum cost to reach
// top right corner from bottom left corner
import java.util.*;
class GFG
{
static int ROW = 3;
static int COL = 3;
// To store matrix cell coordinates
static class Point
{
int x;
int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Check whether given cell (row, col)
// is a valid cell or not.
static boolean isValid(Point p)
{
// Return true if row number and column number
// is in range
return (p.x >= 0) && (p.y < COL);
}
// Function to find maximum cost to reach
// top right corner from bottom left corner
static int find_max_cost(int mat[][])
{
int [][]max_val = new int[ROW][COL];
max_val[ROW - 1][0] = mat[ROW - 1][0];
// Starting point
Point src = new Point(ROW - 1, 0);
// Create a queue for traversal
Queue<Point> q = new LinkedList<>();
q.add(src); // Enqueue source cell
// Do a BFS starting from source cell
// on the allowed direction
while (!q.isEmpty())
{
Point curr = q.peek();
q.remove();
// Find up point
Point up = new Point(curr.x - 1, curr.y);
// if adjacent cell is valid, enqueue it.
if (isValid(up))
{
max_val[up.x][up.y] = Math.max(max_val[up.x][up.y],
mat[up.x][up.y] + max_val[curr.x][curr.y]);
q.add(up);
}
// Find right point
Point right = new Point(curr.x, curr.y + 1);
if(isValid(right))
{
max_val[right.x][right.y] = Math.max(max_val[right.x][right.y],
mat[right.x][right.y] + max_val[curr.x][curr.y]);
q.add(right);
}
}
// Return the required answer
return max_val[0][COL - 1];
}
// Driver code
public static void main(String[] args)
{
int mat[][] = {{20, -10, 0},
{1, 5, 10},
{1, 2, 3}};
System.out.println("Given matrix is ");
for(int i = 0 ; i < ROW; ++i)
{
for(int j = 0; j < COL; ++j)
System.out.print(mat[i][j] + " ");
System.out.println();
}
System.out.print("Maximum cost is " +
find_max_cost(mat));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find maximum cost to reach
# top right corner from bottom left corner
from collections import deque as queue
ROW = 3
COL = 3
# Check whether given cell (row, col)
# is a valid cell or not.
def isValid(p):
# Return true if row number and column number
# is in range
return (p[0] >= 0) and (p[1] < COL)
# Function to find maximum cost to reach
# top right corner from bottom left corner
def find_max_cost(mat):
max_val = [[0 for i in range(COL)] for i in range(ROW)]
max_val[ROW - 1][0] = mat[ROW - 1][0]
# Starting po
src = [ROW - 1, 0]
# Create a queue for traversal
q = queue()
q.appendleft(src) # Enqueue source cell
# Do a BFS starting from source cell
# on the allowed direction
while (len(q) > 0):
curr = q.pop()
# Find up point
up = [curr[0] - 1, curr[1]]
# if adjacent cell is valid, enqueue it.
if (isValid(up)):
max_val[up[0]][up[1]] = max(max_val[up[0]][up[1]],mat[up[0]][up[1]] + max_val[curr[0]][curr[1]])
q.appendleft(up)
# Find right po
right = [curr[0], curr[1] + 1]
if(isValid(right)):
max_val[right[0]][right[1]] = max(max_val[right[0]][right[1]],mat[right[0]][right[1]] + max_val[curr[0]][curr[1]])
q.appendleft(right)
# Return the required answer
return max_val[0][COL - 1]
# Driver code
mat = [[20, -10, 0],
[1, 5, 10],
[1, 2, 3]]
print("Given matrix is ")
for i in range(ROW):
for j in range(COL):
print(mat[i][j],end=" ")
print()
print("Maximum cost is ", find_max_cost(mat))
# This code is contributed by mohit kumar 29
C#
// C# program to find maximum cost to reach
// top right corner from bottom left corner
using System;
using System.Collections.Generic;
class GFG
{
static int ROW = 3;
static int COL = 3;
// To store matrix cell coordinates
public class Point
{
public int x;
public int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Check whether given cell (row, col)
// is a valid cell or not.
static Boolean isValid(Point p)
{
// Return true if row number and
// column number is in range
return (p.x >= 0) && (p.y < COL);
}
// Function to find maximum cost to reach
// top right corner from bottom left corner
static int find_max_cost(int [,]mat)
{
int [,]max_val = new int[ROW,COL];
max_val[ROW - 1, 0] = mat[ROW - 1, 0];
// Starting point
Point src = new Point(ROW - 1, 0);
// Create a queue for traversal
Queue<Point> q = new Queue<Point>();
q.Enqueue(src); // Enqueue source cell
// Do a BFS starting from source cell
// on the allowed direction
while (q.Count != 0)
{
Point curr = q.Peek();
q.Dequeue();
// Find up point
Point up = new Point(curr.x - 1, curr.y);
// if adjacent cell is valid, enqueue it.
if (isValid(up))
{
max_val[up.x, up.y] = Math.Max(max_val[up.x, up.y],
mat[up.x, up.y] + max_val[curr.x, curr.y]);
q.Enqueue(up);
}
// Find right point
Point right = new Point(curr.x,
curr.y + 1);
if(isValid(right))
{
max_val[right.x, right.y] = Math.Max(max_val[right.x, right.y],
mat[right.x, right.y] + max_val[curr.x, curr.y]);
q.Enqueue(right);
}
}
// Return the required answer
return max_val[0, COL - 1];
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = {{20, -10, 0},
{1, 5, 10},
{1, 2, 3}};
Console.WriteLine("Given matrix is ");
for(int i = 0 ; i < ROW; ++i)
{
for(int j = 0; j < COL; ++j)
Console.Write(mat[i, j] + " ");
Console.WriteLine();
}
Console.Write("Maximum cost is " +
find_max_cost(mat));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find maximum cost to reach
// top right corner from bottom left corner
let ROW = 3;
let COL = 3;
// To store matrix cell coordinates
class Point
{
constructor(x, y)
{
this.x = x;
this.y = y;
}
}
// Check whether given cell (row, col)
// is a valid cell or not.
function isValid(p)
{
// Return true if row number and column
// number is in range
return (p.x >= 0) && (p.y < COL);
}
// Function to find maximum cost to reach
// top right corner from bottom left corner
function find_max_cost(mat)
{
let max_val = new Array(ROW);
for(let i = 0; i < ROW; i++)
{
max_val[i] = new Array(COL);
for(let j = 0; j < COL; j++)
{
max_val[i][j] = 0;
}
}
max_val[ROW - 1][0] = mat[ROW - 1][0];
// Starting point
let src = new Point(ROW - 1, 0);
// Create a queue for traversal
let q = [];
// Enqueue source cell
q.push(src);
// Do a BFS starting from source cell
// on the allowed direction
while (q.length != 0)
{
let curr = q.shift();
// Find up point
let up = new Point(curr.x - 1, curr.y);
// If adjacent cell is valid, enqueue it.
if (isValid(up))
{
max_val[up.x][up.y] = Math.max(max_val[up.x][up.y],
mat[up.x][up.y] + max_val[curr.x][curr.y]);
q.push(up);
}
// Find right point
let right = new Point(curr.x, curr.y + 1);
if(isValid(right))
{
max_val[right.x][right.y] = Math.max(max_val[right.x][right.y],
mat[right.x][right.y] + max_val[curr.x][curr.y]);
q.push(right);
}
}
// Return the required answer
return max_val[0][COL - 1];
}
// Driver code
let mat = [ [ 20, -10, 0 ],
[ 1, 5, 10 ],
[ 1, 2, 3 ] ];
document.write("Given matrix is <br>");
for(let i = 0; i < ROW; ++i)
{
for(let j = 0; j < COL; ++j)
document.write(mat[i][j] + " ");
document.write("<br>");
}
document.write("Maximum cost is " +
find_max_cost(mat));
// This code is contributed by patel2127
</script>
Producción:
Given matrix is 20 -10 0 1 5 10 1 2 3 Maximum cost is 18
Complejidad de Tiempo: O(ROW * COL)
Espacio Auxiliar: O(ROW * COL)
Publicación traducida automáticamente
Artículo escrito por Rahul_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA