// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

#include <limits>
#define INFINITO numeric_limits<float>::infinity()

using namespace std;

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
float minimaEnergia(const vector<vector<float> > & energiaCelda,
                    const vector<vector<float> > & energiaSalto,
		    int fila,
		    int columna) {

   // Minima energia necesaria para llegar hasta la celda (fila, columna) desde la ultima fila

   float resultado;
   
   int filas = energiaCelda.size();
   int columnas = energiaCelda[0].size();
   
   if (fila == filas - 1)
      resultado = energiaCelda[fila][columna];
   else {
      float minimo = INFINITO;
      for (int otraColumna = 0; otraColumna < columnas; otraColumna++)
	 minimo = min(minimo,
		      minimaEnergia(energiaCelda, energiaSalto, fila + 1, otraColumna)
		      + energiaSalto[otraColumna][columna]
                      + energiaCelda[fila][columna]);
      resultado = minimo;
   }
   
   return resultado;
   
}

float minimaEnergia(const vector<vector<float> > & energiaCelda,
                    const vector<vector<float> > & energiaSalto) {
   
   int columnas = energiaCelda[0].size();

   float minimo = INFINITO;
   for (int columna = 0; columna < columnas; columna++)
      minimo = min(minimo,
		   minimaEnergia(energiaCelda, energiaSalto, 0, columna));
		   
   return minimo;
		   
}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

float minimaEnergia(const vector<vector<float> > & energiaCelda,
                    const vector<vector<float> > & energiaSalto,
		    int fila,
		    int columna,
		    vector<vector<float> > & resultado) {

   if (resultado[fila][columna] == DESCONOCIDO) {
   
      int filas = energiaCelda.size();
      int columnas = energiaCelda[0].size();
   
      if (fila == filas - 1)
	 resultado[fila][columna] = energiaCelda[fila][columna];
      else {
	 float minimo = INFINITO;
	 for (int otraColumna = 0; otraColumna < columnas; otraColumna++)
	    minimo = min(minimo,
			 minimaEnergia(energiaCelda, energiaSalto, fila + 1, otraColumna, resultado)
			 + energiaSalto[otraColumna][columna]
			 + energiaCelda[fila][columna]);
	 resultado[fila][columna] = minimo;
      }
   }
   
   return resultado[fila][columna];
   
}

float minimaEnergia(const vector<vector<float> > & energiaCelda,
                    const vector<vector<float> > & energiaSalto) {
   
   int filas = energiaCelda.size();
   int columnas = energiaCelda[0].size();

   vector<vector<float> > resultado(filas, vector<float>(columnas, DESCONOCIDO));

   float minimo = INFINITO;
   for (int columna = 0; columna < columnas; columna++)
      minimo = min(minimo,
		   minimaEnergia(energiaCelda, energiaSalto, 0, columna, resultado));
		   
   return minimo;
		   
}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
float minimaEnergia(const vector<vector<float> > & energiaCelda,
                    const vector<vector<float> > & energiaSalto) {
   
   int filas = energiaCelda.size();
   int columnas = energiaCelda[0].size();

   vector<vector<float> > resultado(filas, vector<float>(columnas));

   for (int fila = filas - 1; fila >= 0; fila--)
      for (int columna = 0; columna < columnas; columna++)
	 if (fila == filas - 1)
	    resultado[fila][columna] = energiaCelda[fila][columna];
	 else {
	    float minimo = INFINITO;
	    for (int otraColumna = 0; otraColumna < columnas; otraColumna++)
	       minimo = min(minimo,
			    resultado[fila + 1][otraColumna]
			    + energiaSalto[otraColumna][columna]
			    + energiaCelda[fila][columna]);
	    resultado[fila][columna] = minimo;
	 }

   float minimo = INFINITO;
   for (int columna = 0; columna < columnas; columna++)
      minimo = min(minimo,
		   resultado[0][columna]);
		   
   return minimo;
		   
}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main () {

   vector<vector<float> > ejemploEnergiaCelda = { {30, 40, 90, 80},
						  {20, 20, 10, 30},
						  {70, 50, 90, 70},
						  {60, 30, 10, 20},
						  {50, 90, 30, 60},
						  {40, 60, 50, 90} };

   vector<vector<float> > ejemploEnergiaSalto = { {0, 35, 85, 25},
						  {5,  0, 45, 15},
						  {65, 75, 0, 25},
						  {95, 25, 15, 0} };

   float resultado = minimaEnergia(ejemploEnergiaCelda, ejemploEnergiaSalto);
   cout << "Energia minima: " << resultado << endl;
   if (resultado == 255)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}