// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

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

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

/*
float maxPuntos(const vector<vector<float> > & puntos,
		int fila,
		int columna) {

   // Maxima cantidad de puntos que puede acumular el jugador desde la celda (0, 0)
   // hasta la celda (fila, columna)
   
   float resultado;
   
   if (puntos[fila][columna] == -1)
      resultado = -INFINITO; // La suma de -infinity() con cualquier puntuacion vuelve a
                             // dar -infinity().  Si el resultado final es -infinity()
                             // significara que la celda final es inalcanzable.

   else if (fila == 0 && columna == 0)
      resultado = puntos[fila][columna];

   else if (fila == 0)
      resultado = puntos[fila][columna] + maxPuntos(puntos, fila, columna - 1);

   else if (columna == 0)
      resultado = puntos[fila][columna] + maxPuntos(puntos, fila - 1, columna);

   else
      resultado = puntos[fila][columna] + max(maxPuntos(puntos, fila, columna - 1),
					      maxPuntos(puntos, fila - 1, columna));

   return resultado;

}

float maxPuntos(const vector<vector<float> > & puntos) {

   int cantidadDeFilas = puntos.size(), cantidadDeColumnas = puntos[0].size();
   return maxPuntos(puntos, cantidadDeFilas - 1, cantidadDeColumnas - 1);

}
*/

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

/*
#define DESCONOCIDO -1

float maxPuntos(const vector<vector<float> > & puntos,
		int fila,
		int columna,
		vector<vector<float> > & resultado) {
   
   if (resultado[fila][columna] == DESCONOCIDO)

      if (puntos[fila][columna] == -1)
         resultado[fila][columna] = -INFINITO;

      else if (fila == 0 && columna == 0)
         resultado[fila][columna] = puntos[fila][columna];

      else if (fila == 0)
         resultado[fila][columna] = puntos[fila][columna] + maxPuntos(puntos, fila, columna - 1, resultado);

      else if (columna == 0)
         resultado[fila][columna] = puntos[fila][columna] + maxPuntos(puntos, fila - 1, columna, resultado);

      else
         resultado[fila][columna] = puntos[fila][columna] + max(maxPuntos(puntos, fila, columna - 1, resultado),
	                                                        maxPuntos(puntos, fila - 1, columna, resultado));

   return resultado[fila][columna];

}

float maxPuntos(const vector<vector<float> > & puntos) {

   int cantidadDeFilas = puntos.size(), cantidadDeColumnas = puntos[0].size();
   vector<vector<float> > resultado(cantidadDeFilas, vector<float>(cantidadDeColumnas, DESCONOCIDO));
   return maxPuntos(puntos, cantidadDeFilas - 1, cantidadDeColumnas - 1, resultado);

}
*/

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

/*
float maxPuntos(const vector<vector<float> > & puntos) {

   int cantidadDeFilas = puntos.size(), cantidadDeColumnas = puntos[0].size();
   vector<vector<float> > resultado(cantidadDeFilas, vector<float>(cantidadDeColumnas));

   for (int fila = 0; fila < cantidadDeFilas; fila++)

      for (int columna = 0; columna < cantidadDeColumnas; columna++)
	 
	 if (puntos[fila][columna] == -1)
	    resultado[fila][columna] = -INFINITO;
   
	 else if (fila == 0 && columna == 0)
	    resultado[fila][columna] = puntos[fila][columna];
   
	 else if (fila == 0)
	    resultado[fila][columna] = puntos[fila][columna] + resultado[fila][columna - 1];
   
	 else if (columna == 0)
	    resultado[fila][columna] = puntos[fila][columna] + resultado[fila - 1][columna];
   
	 else
	    resultado[fila][columna] = puntos[fila][columna] + max(resultado[fila][columna - 1],
                                                                   resultado[fila - 1][columna]);

   return resultado[cantidadDeFilas - 1][cantidadDeColumnas - 1];

}
*/

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

int main() {

   vector<vector<float> > ejemplo = { {3,  0, 0,  0,  0,  0,  0,  0,  0, 0,  0,  0,  0, 0, 0},
				      {0,  5, 0,  0,  0,  0,  0,  0,  0, 0, -1, -1, -1, 0, 0},
				      {0,  0, 0, -1, -1,  1,  3, -1, -1, 0,  0,  0, -1, 0, 0},
				      {0,  5, 0,  9, -1,  2,  4, -1,  9, 0,  0,  0, -1, 0, 0},
				      {-1, 0, 0,  0,  0,  0,  0,  0,  0, 0,  0,  0, -1, 0, 5},
				      {-1, 0, 0,  3,  2, -1, -1,  2,  3, 0,  0,  0, -1, 0, 0},
				      {-1, 0, 0,  4, -1, -1, -1, -1,  4, 0,  0,  0, -1, 0, 5},
				      {0,  0, 0, -1, -1, -1, -1, -1, -1, 0,  0,  0, -1, 0, 0},
				      {7,  0, 0,  1,  1,  1,  1,  1,  1, 0,  0,  0, -1, 0, 5},
				      {0,  0, 0,  0, -1, -1, -1, -1,  1, 1,  1,  1,  1, 2, 4}
   };
   
   float cantidadMaxima = maxPuntos(ejemplo);
   cout << "Cantidad de puntos maxima: " << cantidadMaxima << endl;
   if (cantidadMaxima == 41)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;
				     
}