Dada una cuadrícula bidimensional, cada celda de la cual contiene un costo entero que representa un costo para atravesar esa celda, necesitamos encontrar un camino desde la celda superior izquierda hasta la celda inferior derecha por el cual el costo total incurrido sea mínimo.
Nota: Se supone que los ciclos de costos negativos no existen en la array de entrada.
Este problema es una extensión del problema: Min Cost Path con movimientos hacia la derecha y hacia abajo permitidos.
En el problema anterior, solo se permitía ir a la derecha y abajo, pero en este problema, se nos permite ir abajo, arriba, derecha e izquierda, es decir, en las 4 direcciones.
Ejemplos:
A cost grid is given in below diagram, minimum cost to reach bottom right from top left is 327 (= 31 + 10 + 13 + 47 + 65 + 12 + 18 + 6 + 33 + 11 + 20 + 41 + 20) The chosen least cost path is shown in green.
No es posible resolver este problema utilizando una programación dinámica similar al problema anterior porque aquí el estado actual depende no solo de las celdas derecha e inferior sino también de las celdas izquierda y superior. Resolvemos este problema usando el algoritmo de Dijkstra . Cada celda de la cuadrícula representa un vértice y las celdas vecinas vértices adyacentes. No hacemos un gráfico explícito a partir de estas celdas, sino que usaremos la array tal como está en nuestro algoritmo de Dijkstra.
En el siguiente código, se utiliza la implementación del algoritmo de Dijkstra. El código implementado a continuación se cambia para hacer frente al gráfico implícito representado por array. Consulte también el uso de arrays dx y dy en el siguiente código, estas arrays se toman para simplificar el proceso de visitar los vértices vecinos de cada celda.
Implementación:
C++
// C++ program to get least cost path in a grid from
// top-left to bottom-right
#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
// structure for information of each cell
struct cell {
int x, y;
int distance;
cell(int x, int y, int distance)
: x(x)
, y(y)
, distance(distance)
{
}
};
// Utility method for comparing two cells
bool operator<(const cell& a, const cell& b)
{
if (a.distance == b.distance) {
if (a.x != b.x)
return (a.x < b.x);
else
return (a.y < b.y);
}
return (a.distance < b.distance);
}
// Utility method to check whether a point is
// inside the grid or not
bool isInsideGrid(int i, int j)
{
return (i >= 0 && i < ROW && j >= 0 && j < COL);
}
// Method returns minimum cost to reach bottom
// right from top left
int shortest(int grid[ROW][COL], int row, int col)
{
int dis[row][col];
// initializing distance array by INT_MAX
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
dis[i][j] = INT_MAX;
// direction arrays for simplification of getting
// neighbour
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
set<cell> st;
// insert (0, 0) cell with 0 distance
st.insert(cell(0, 0, 0));
// initialize distance of (0, 0) with its grid value
dis[0][0] = grid[0][0];
// loop for standard dijkstra's algorithm
while (!st.empty()) {
// get the cell with minimum distance and delete
// it from the set
cell k = *st.begin();
st.erase(st.begin());
// looping through all neighbours
for (int i = 0; i < 4; i++) {
int x = k.x + dx[i];
int y = k.y + dy[i];
// if not inside boundary, ignore them
if (!isInsideGrid(x, y))
continue;
// If distance from current cell is smaller,
// then update distance of neighbour cell
if (dis[x][y] > dis[k.x][k.y] + grid[x][y]) {
// If cell is already there in set, then
// remove its previous entry
if (dis[x][y] != INT_MAX)
st.erase(
st.find(cell(x, y, dis[x][y])));
// update the distance and insert new
// updated cell in set
dis[x][y] = dis[k.x][k.y] + grid[x][y];
st.insert(cell(x, y, dis[x][y]));
}
}
}
// uncomment below code to print distance
// of each cell from (0, 0)
/*
for (int i = 0; i < row; i++, cout << endl)
for (int j = 0; j < col; j++)
cout << dis[i][j] << " ";
*/
// dis[row - 1][col - 1] will represent final
// distance of bottom right cell from top left cell
return dis[row - 1][col - 1];
}
// Driver code to test above methods
int main()
{
int grid[ROW][COL]
= { 31, 100, 65, 12, 18, 10, 13, 47, 157,
6, 100, 113, 174, 11, 33, 88, 124, 41,
20, 140, 99, 32, 111, 41, 20 };
cout << shortest(grid, ROW, COL) << endl;
return 0;
}
Java
// Java program to get least cost path
// in a grid from top-left to bottom-right
import java.io.*;
import java.util.*;
class GFG{
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static int ROW = 5;
static int COL = 5;
// Custom class for representing
// row-index, column-index &
// distance of each cell
static class Cell
{
int x;
int y;
int distance;
Cell(int x, int y, int distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
}
// Custom comparator for inserting cells
// into Priority Queue
static class distanceComparator
implements Comparator<Cell>
{
public int compare(Cell a, Cell b)
{
if (a.distance < b.distance)
{
return -1;
}
else if (a.distance > b.distance)
{
return 1;
}
else {return 0;}
}
}
// Utility method to check whether current
// cell is inside grid or not
static boolean isInsideGrid(int i, int j)
{
return (i >= 0 && i < ROW &&
j >= 0 && j < COL);
}
// Method to return shortest path from
// top-corner to bottom-corner in 2D grid
static int shortestPath(int[][] grid, int row,
int col)
{
int[][] dist = new int[row][col];
// Initializing distance array by INT_MAX
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
dist[i][j] = Integer.MAX_VALUE;
}
}
// Initialized source distance as
// initial grid position value
dist[0][0] = grid[0][0];
PriorityQueue<Cell> pq = new PriorityQueue<Cell>(
row * col, new distanceComparator());
// Insert source cell to priority queue
pq.add(new Cell(0, 0, dist[0][0]));
while (!pq.isEmpty())
{
Cell curr = pq.poll();
for(int i = 0; i < 4; i++)
{
int rows = curr.x + dx[i];
int cols = curr.y + dy[i];
if (isInsideGrid(rows, cols))
{
if (dist[rows][cols] >
dist[curr.x][curr.y] +
grid[rows][cols])
{
// If Cell is already been reached once,
// remove it from priority queue
if (dist[rows][cols] != Integer.MAX_VALUE)
{
Cell adj = new Cell(rows, cols,
dist[rows][cols]);
pq.remove(adj);
}
// Insert cell with updated distance
dist[rows][cols] = dist[curr.x][curr.y] +
grid[rows][cols];
pq.add(new Cell(rows, cols,
dist[rows][cols]));
}
}
}
}
return dist[row - 1][col - 1];
}
// Driver code
public static void main(String[] args)
throws IOException
{
int[][] grid = { { 31, 100, 65, 12, 18 },
{ 10, 13, 47, 157, 6 },
{ 100, 113, 174, 11, 33 },
{ 88, 124, 41, 20, 140 },
{ 99, 32, 111, 41, 20 } };
System.out.println(shortestPath(grid, ROW, COL));
}
}
// This code is contributed by jigyansu
Python3
# Python program to get least cost path in a grid from # top-left to bottom-right from functools import cmp_to_key ROW = 5 COL = 5 def mycmp(a,b): if (a.distance == b.distance): if (a.x != b.x): return (a.x - b.x) else: return (a.y - b.y) return (a.distance - b.distance) # structure for information of each cell class cell: def __init__(self,x, y, distance): self.x = x self.y = y self.distance = distance # Utility method to check whether a point is # inside the grid or not def isInsideGrid(i, j): return (i >= 0 and i < ROW and j >= 0 and j < COL) # Method returns minimum cost to reach bottom # right from top left def shortest(grid, row, col): dis = [[0 for i in range(col)]for j in range(row)] # initializing distance array by INT_MAX for i in range(row): for j in range(col): dis[i][j] = 1000000000 # direction arrays for simplification of getting # neighbour dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] st = [] # insert (0, 0) cell with 0 distance st.append(cell(0, 0, 0)) # initialize distance of (0, 0) with its grid value dis[0][0] = grid[0][0] # loop for standard dijkstra's algorithm while (len(st)!=0): # get the cell with minimum distance and delete # it from the set k = st[0] st = st[1:] # looping through all neighbours for i in range(4): x = k.x + dx[i] y = k.y + dy[i] # if not inside boundary, ignore them if (isInsideGrid(x, y) == 0): continue # If distance from current cell is smaller, then # update distance of neighbour cell if (dis[x][y] > dis[k.x][k.y] + grid[x][y]): # update the distance and insert new updated # cell in set dis[x][y] = dis[k.x][k.y] + grid[x][y] st.append(cell(x, y, dis[x][y])) st.sort(key=cmp_to_key(mycmp)) # uncomment below code to print distance # of each cell from (0, 0) # for i in range(row): # for j in range(col): # print(dis[i][j] ,end= " ") # print() # dis[row - 1][col - 1] will represent final # distance of bottom right cell from top left cell return dis[row - 1][col - 1] # Driver code to test above methods grid = [[31, 100, 65, 12, 18], [10, 13, 47, 157, 6], [100, 113, 174, 11, 33], [88, 124, 41, 20, 140],[99, 32, 111, 41, 20]] print(shortest(grid, ROW, COL)) # This code is contributed by shinjanpatra
Javascript
<script>
// Javascript program to get least cost path in a grid from
// top-left to bottom-right
var ROW = 5
var COL = 5
// structure for information of each cell
class cell
{
constructor(x, y, distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
};
// Utility method to check whether a point is
// inside the grid or not
function isInsideGrid(i, j)
{
return (i >= 0 && i < ROW && j >= 0 && j < COL);
}
// Method returns minimum cost to reach bottom
// right from top left
function shortest(grid, row, col)
{
var dis = Array.from(Array(row), ()=>Array(col).fill(0));
// initializing distance array by INT_MAX
for (var i = 0; i < row; i++)
for (var j = 0; j < col; j++)
dis[i][j] = 1000000000;
// direction arrays for simplification of getting
// neighbour
var dx = [-1, 0, 1, 0];
var dy = [0, 1, 0, -1];
var st = [];
// insert (0, 0) cell with 0 distance
st.push(new cell(0, 0, 0));
// initialize distance of (0, 0) with its grid value
dis[0][0] = grid[0][0];
// loop for standard dijkstra's algorithm
while (st.length!=0)
{
// get the cell with minimum distance and delete
// it from the set
var k = st[0];
st.shift();
// looping through all neighbours
for (var i = 0; i < 4; i++)
{
var x = k.x + dx[i];
var y = k.y + dy[i];
// if not inside boundary, ignore them
if (!isInsideGrid(x, y))
continue;
// If distance from current cell is smaller, then
// update distance of neighbour cell
if (dis[x][y] > dis[k.x][k.y] + grid[x][y])
{
// update the distance and insert new updated
// cell in set
dis[x][y] = dis[k.x][k.y] + grid[x][y];
st.push(new cell(x, y, dis[x][y]));
}
}
st.sort((a,b)=>{
if (a.distance == b.distance)
{
if (a.x != b.x)
return (a.x - b.x);
else
return (a.y - b.y);
}
return (a.distance - b.distance);
});
}
// uncomment below code to print distance
// of each cell from (0, 0)
/*
for (int i = 0; i < row; i++, cout << endl)
for (int j = 0; j < col; j++)
cout << dis[i][j] << " ";
*/
// dis[row - 1][col - 1] will represent final
// distance of bottom right cell from top left cell
return dis[row - 1][col - 1];
}
// Driver code to test above methods
var grid =
[
[31, 100, 65, 12, 18],
[10, 13, 47, 157, 6],
[100, 113, 174, 11, 33],
[88, 124, 41, 20, 140],
[99, 32, 111, 41, 20]
];
document.write(shortest(grid, ROW, COL));
// This code is contributed by rutvik_56.
</script>
Producción
327
Complejidad del tiempo: O(n^2)
Complejidad espacial: O(n^2)
Este artículo es una contribución de Utkarsh Trivedi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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