Dada una array, la tarea es encontrar el costo del camino mínimo que es impar para llegar al fondo de una array. Si no existe tal ruta, imprima -1.
Nota: Solo se permiten movimientos de abajo a la derecha, de abajo a la izquierda y de abajo directos.
Ejemplos:
Input: mat[] =
{{ 1, 2, 3, 4, 6},
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 100, 2, 3, 4, 5 }
Output: 11
Input: mat[][] =
{{1, 5, 2},
{7, 2, 2},
{2, 8, 1}}
Output: 5
Enfoque: Este problema se puede resolver usando programación dinámica:
Para la primera fila (caso base), el costo es
piso[0][j]=dado[0][j] (piso es nuestra array de costos y dado es nuestra array dada)
// Para la mayoría de los elementos de la izquierda
if(j==0)
piso[i][j]=dado[i][j]+min(piso[i-1][j], piso[i-1][j+ 1]);
// Para el elemento más a la derecha
else if(j == N-1)
piso[i][j] = dado[i][j] + min(piso[i-1][j], piso[i-1][ j-1])
- Como cualquier elemento, excepto el más a la izquierda y el más a la derecha, se puede acceder directamente desde el bloque de la fila superior o superior izquierda o superior derecha. Asi que,
else
piso[i][j] = a[i][j] + min(piso[i-1][j-1] + piso[i-1][j] + piso[i-1][j+ 1])
Por último, devuelva el valor impar mínimo de la última fila. En caso de que no esté presente, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Minimum
// odd cost path in a matrix
#include <bits/stdc++.h>
#define M 100 // number of rows
#define N 100 // number of columns
using namespace std;
// Function to find the minimum cost
int find_min_odd_cost(int given[M][N], int m, int n)
{
int floor[M][N] = { { 0 }, { 0 } };
int min_odd_cost = 0;
int i, j, temp;
for (j = 0; j < n; j++)
floor[0][j] = given[0][j];
for (i = 1; i < m; i++)
for (j = 0; j < n; j++) {
// leftmost element
if (j == 0) {
floor[i][j] = given[i][j];
floor[i][j] += min(floor[i - 1][j], floor[i - 1][j + 1]);
}
// rightmost element
else if (j == n - 1) {
floor[i][j] = given[i][j];
floor[i][j] += min(floor[i - 1][j], floor[i - 1][j - 1]);
}
// Any element except leftmost and rightmost element of a row
// is reachable from direct upper or left upper or right upper
// row's block
else {
// Counting the minimum cost
temp = min(floor[i - 1][j], floor[i - 1][j - 1]);
temp = min(temp, floor[i - 1][j + 1]);
floor[i][j] = given[i][j] + temp;
}
}
min_odd_cost = INT_MAX;
// Find the minimum cost
for (j = 0; j < n; j++) {
if (floor[n - 1][j] % 2 == 1) {
if (min_odd_cost > floor[n - 1][j])
min_odd_cost = floor[n - 1][j];
}
}
if (min_odd_cost == INT_MIN)
return -1;
return min_odd_cost;
}
// Driver code
int main()
{
int m = 5, n = 5;
int given[M][N] = { { 1, 2, 3, 4, 6 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 100, 2, 3, 4, 5 } };
cout << "Minimum odd cost is "
<< find_min_odd_cost(given, m, n);
return 0;
}
Java
// Java program to find minimum odd
// cost path in a matrix
public class GFG {
public static final int M = 100 ;
public static final int N = 100 ;
// Function to find the minimum cost
static int find_min_odd_cost(int given[][], int m, int n)
{
int floor[][] = new int [M][N];
int min_odd_cost = 0;
int i, j, temp;
for (j = 0; j < n; j++)
floor[0][j] = given[0][j];
for (i = 1; i < m; i++)
for (j = 0; j < n; j++) {
// leftmost element
if (j == 0) {
floor[i][j] = given[i][j];
floor[i][j] += Math.min(floor[i - 1][j], floor[i - 1][j + 1]);
}
// rightmost element
else if (j == n - 1) {
floor[i][j] = given[i][j];
floor[i][j] += Math.min(floor[i - 1][j], floor[i - 1][j - 1]);
}
// Any element except leftmost and rightmost element of a row
// is reachable from direct upper or left upper or right upper
// row's block
else {
// Counting the minimum cost
temp = Math.min(floor[i - 1][j], floor[i - 1][j - 1]);
temp = Math.min(temp, floor[i - 1][j + 1]);
floor[i][j] = given[i][j] + temp;
}
}
min_odd_cost = Integer.MAX_VALUE;
// Find the minimum cost
for (j = 0; j < n; j++) {
if (floor[n - 1][j] % 2 == 1) {
if (min_odd_cost > floor[n - 1][j])
min_odd_cost = floor[n - 1][j];
}
}
if (min_odd_cost == Integer.MIN_VALUE)
return -1;
return min_odd_cost;
}
// Driver code
public static void main(String args[])
{
int m = 5, n = 5;
int given[][] = { { 1, 2, 3, 4, 6 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 100, 2, 3, 4, 5 } };
System.out.println( "Minimum odd cost is " + find_min_odd_cost(given, m, n));
}
// This Code is contributed by ANKITRAI1
}
Python3
# Python3 program to find Minimum
# odd cost path in a matrix
M = 100 # number of rows
N = 100 # number of columns
# Function to find the minimum cost
def find_min_odd_cost(given, m, n):
floor = [[0 for i in range(M)]
for i in range(N)]
min_odd_cost = 0
i, j, temp = 0, 0, 0
for j in range(n):
floor[0][j] = given[0][j]
for i in range(1, m):
for j in range(n):
# leftmost element
if (j == 0):
floor[i][j] = given[i][j];
floor[i][j] += min(floor[i - 1][j],
floor[i - 1][j + 1])
# rightmost element
elif (j == n - 1):
floor[i][j] = given[i][j];
floor[i][j] += min(floor[i - 1][j],
floor[i - 1][j - 1])
# Any element except leftmost and rightmost
# element of a row is reachable from direct
# upper or left upper or right upper row's block
else:
# Counting the minimum cost
temp = min(floor[i - 1][j],
floor[i - 1][j - 1])
temp = min(temp, floor[i - 1][j + 1])
floor[i][j] = given[i][j] + temp
min_odd_cost = 10**9
# Find the minimum cost
for j in range(n):
if (floor[n - 1][j] % 2 == 1):
if (min_odd_cost > floor[n - 1][j]):
min_odd_cost = floor[n - 1][j]
if (min_odd_cost == -10**9):
return -1;
return min_odd_cost
# Driver code
m, n = 5, 5
given = [[ 1, 2, 3, 4, 6 ],
[ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ],
[ 100, 2, 3, 4, 5 ]]
print("Minimum odd cost is",
find_min_odd_cost(given, m, n))
# This code is contributed by mohit kumar
C#
// C# program to find minimum odd
// cost path in a matrix
using System;
public class GFG {
public static int M = 100 ;
public static int N = 100 ;
// Function to find the minimum cost
static int find_min_odd_cost(int[,] given, int m, int n)
{
int[,] floor = new int [M,N];
int min_odd_cost = 0;
int i, j, temp;
for (j = 0; j < n; j++)
floor[0,j] = given[0,j];
for (i = 1; i < m; i++)
for (j = 0; j < n; j++) {
// leftmost element
if (j == 0) {
floor[i,j] = given[i,j];
floor[i,j] += Math.Min(floor[i - 1,j], floor[i - 1,j + 1]);
}
// rightmost element
else if (j == n - 1) {
floor[i,j] = given[i,j];
floor[i,j] += Math.Min(floor[i - 1,j], floor[i - 1,j - 1]);
}
// Any element except leftmost and rightmost element of a row
// is reachable from direct upper or left upper or right upper
// row's block
else {
// Counting the minimum cost
temp = Math.Min(floor[i - 1,j], floor[i - 1,j - 1]);
temp = Math.Min(temp, floor[i - 1,j + 1]);
floor[i,j] = given[i,j] + temp;
}
}
min_odd_cost = int.MaxValue;
// Find the minimum cost
for (j = 0; j < n; j++) {
if (floor[n - 1,j] % 2 == 1) {
if (min_odd_cost > floor[n - 1,j])
min_odd_cost = floor[n - 1,j];
}
}
if (min_odd_cost == int.MinValue)
return -1;
return min_odd_cost;
}
// Driver code
public static void Main()
{
int m = 5, n = 5;
int[,] given = { { 1, 2, 3, 4, 6 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 1, 2, 3, 4, 5 },
{ 100, 2, 3, 4, 5 } };
Console.Write( "Minimum odd cost is " +
find_min_odd_cost(given, m, n));
}
}
PHP
<?php
// PHP program to find Minimum
// odd cost path in a matrix
$M = 100; $N = 100;
// Function to find the minimum cost
function find_min_odd_cost($given, $m, $n)
{
global $M, $N;
$floor1[$M][$N] = array(array(0),
array(0));
$min_odd_cost = 0;
for ($j = 0; $j < $n; $j++)
$floor1[0][$j] = $given[0][$j];
for ($i = 1; $i < $m; $i++)
for ($j = 0; $j < $n; $j++)
{
// leftmost element
if ($j == 0)
{
$floor1[$i][$j] = $given[$i][$j];
$floor1[$i][$j] += min($floor1[$i - 1][$j],
$floor1[$i - 1][$j + 1]);
}
// rightmost element
else if ($j == $n - 1)
{
$floor1[$i][$j] = $given[$i][$j];
$floor1[$i][$j] += min($floor1[$i - 1][$j],
$floor1[$i - 1][$j - 1]);
}
// Any element except leftmost and rightmost
// element of a row is reachable from direct
// upper or left upper or right upper row's block
else
{
// Counting the minimum cost
$temp = min($floor1[$i - 1][$j],
$floor1[$i - 1][$j - 1]);
$temp = min($temp, $floor1[$i - 1][$j + 1]);
$floor1[$i][$j] = $given[$i][$j] + $temp;
}
}
$min_odd_cost = PHP_INT_MAX;
// Find the minimum cost
for ($j = 0; $j < $n; $j++)
{
if ($floor1[$n - 1][$j] % 2 == 1)
{
if ($min_odd_cost > $floor1[$n - 1][$j])
$min_odd_cost = $floor1[$n - 1][$j];
}
}
if ($min_odd_cost == PHP_INT_MIN)
return -1;
return $min_odd_cost;
}
// Driver code
$m = 5; $n = 5;
$given = array(array(1, 2, 3, 4, 6),
array(1, 2, 3, 4, 5),
array(1, 2, 3, 4, 5),
array(1, 2, 3, 4, 5),
array(100, 2, 3, 4, 5));
echo "Minimum odd cost is " .
find_min_odd_cost($given, $m, $n);
// This code is contributed by Akanksha Rai
?>
Javascript
<script>
// Javascript program to find minimum odd
// cost path in a matrix
let M = 100 ;
let N = 100 ;
// Function to find the minimum cost
function find_min_odd_cost(given,m,n)
{
let floor = new Array(M);
for(let i=0;i<M;i++)
{
floor[i]=new Array(N);
for(let j=0;j<N;j++)
{
floor[i][j]=0;
}
}
let min_odd_cost = 0;
let i, j, temp;
for (j = 0; j < n; j++)
floor[0][j] = given[0][j];
for (i = 1; i < m; i++)
for (j = 0; j < n; j++) {
// leftmost element
if (j == 0) {
floor[i][j] = given[i][j];
floor[i][j] += Math.min(floor[i - 1][j],
floor[i - 1][j + 1]);
}
// rightmost element
else if (j == n - 1) {
floor[i][j] = given[i][j];
floor[i][j] += Math.min(floor[i - 1][j],
floor[i - 1][j - 1]);
}
// Any element except leftmost and rightmost element of a row
// is reachable from direct upper or left upper or right upper
// row's block
else {
// Counting the minimum cost
temp = Math.min(floor[i - 1][j],
floor[i - 1][j - 1]);
temp = Math.min(temp, floor[i - 1][j + 1]);
floor[i][j] = given[i][j] + temp;
}
}
min_odd_cost = Number.MAX_VALUE;
// Find the minimum cost
for (j = 0; j < n; j++) {
if (floor[n - 1][j] % 2 == 1) {
if (min_odd_cost > floor[n - 1][j])
min_odd_cost = floor[n - 1][j];
}
}
if (min_odd_cost == Number.MIN_VALUE)
return -1;
return min_odd_cost;
}
// Driver code
let m = 5, n = 5;
let given = [[ 1, 2, 3, 4, 6 ],
[ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ],
[ 1, 2, 3, 4, 5 ],
[ 100, 2, 3, 4, 5 ]];
document.write( "Minimum odd cost is " + find_min_odd_cost(given, m, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Minimum odd cost is 11