// 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 (fila, columna)
   // hasta la celda (ultimaFila, ultimaColumna)
   
   float resultado;
   
   int ultimaFila = puntos.size() - 1, ultimaColumna = puntos[0].size() - 1;

   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 == ultimaFila && columna == ultimaColumna)
      resultado = puntos[fila][columna];

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

   else if (columna == ultimaColumna)
      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, 0, 0);

}
*/

/***************************************************************************
 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) {

      int ultimaFila = puntos.size() - 1, ultimaColumna = puntos[0].size() - 1;

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

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

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

      else if (columna == ultimaColumna)
         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, 0, 0, resultado);

}
*/

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

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

   int ultimaFila = puntos.size() - 1, ultimaColumna = puntos[0].size() - 1;
   vector<vector<float> > resultado(ultimaFila + 1, vector<float>(ultimaColumna + 1));

   for (int fila = ultimaFila; fila >= 0; fila--)

      for (int columna = ultimaColumna; columna >= 0; columna--)
	 
	 if (puntos[fila][columna] == -1)
	    resultado[fila][columna] = -INFINITO;
   
	 else if (fila == ultimaFila && columna == ultimaColumna)
	    resultado[fila][columna] = puntos[fila][columna];
   
	 else if (fila == ultimaFila)
	    resultado[fila][columna] = puntos[fila][columna] + resultado[fila][columna + 1];
   
	 else if (columna == ultimaColumna)
	    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[0][0];

}
*/

/***************************************************************************
 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;
				     
}