Escriba un programa C++ (o Java) para hw12_1 para recolectar la cantidad mxima de monedas en un tablero nxm que se trat en la clase. Ejecucin de muestra 0: supongamos que el usuario escribi las siguientes lneas 5 6 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0

Esta es la salida correcta.

Tenga en cuenta que la coordenada de la celda inicial es (1,1) y el destino es (5,6). Su programa debera mostrar el mximo de monedas y la ruta para recolectarlas. Al retroceder desde el celda de destino, si hay ms de una ruta ptima, su solucin siempre debe elegir la ruta de la izquierda, no desde arriba. Monedas mximas: 5 Ruta:(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)- >(3,6)->(4,6)->(5,6)

Ejecucin de muestra 1: supongamos que el usuario escribi las siguientes lneas. Nuevamente, al retroceder desde el lugar de destino, su solucin siempre debe elegir el camino desde la izquierda, no desde arriba, si hay ms de un camino ptimo. 4 5 0 0 0 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 0 0 Esta es la salida correcta. Monedas mximas: 4 Ruta:(1,1)->(2,1)->(3,1)->(3,2)->(3,3)->(3,4)->(3,5)- >(4,5) Ejecucin de muestra 2: supongamos que el usuario escribi las siguientes lneas 3 2 1 1 0 0 0 1 Esta es la salida correcta. Monedas mximas: 3 Ruta:(1,1)->(1,2)->(2,2)->(3,2)