3586 - Programa para el robot 3586 - Programa para el robot 3586 - Programa para el robot

Statistics Sub: 21 | AC: 12 | AC%: 57,14 | Score: 4,26
Created by Olimpiada Cubana de Informática 2016
Added by frankr (2016-03-26)
Limits
Total Time: 20000 MS | Test Time: 2000 MS |Memory: 256 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

En IslaGrande están diseñando un nuevo juego para dispositivos móviles. Este juego es un rompecabezas con reglas relativamente simples. El juego se desarrolla sobre un área rectangular que consiste de N filas con M columnas. Las filas están numeradas de arriba hacia abajo, comenzando por uno, las columnas en las filas están numeradas de izquierda a derecha, comenzando por uno. Cada casilla corresponde a las coordenadas (X, Y), donde X es el número de la fila y Y es el número de la columna. En la casilla de la esquina superior izquierda hay un robot, el cual en un movimiento solamente puede ir hacia la casilla adyacente de abajo o hacia la casilla adyacente a la derecha. Algunas de las casillas del área de juego son peligrosas. Si el robot alcanza una casilla peligrosa deja de funcionar y el juego se pierde. En las otras casillas hay premios. Si el robot alcanza una casilla que contiene premios, el tomará todos los premios de esa casilla. El objetivo del juego es que el robot salga de los límites del área de juego, sin pasar por una casilla peligrosa y recopile tantos premios como sea posible.

No obstante, el robot tiene una memoria limitada, así que él solamente puede almacenar en su memoria un programa consistente de a lo sumo K caracteres-comandos. Un programa es una secuencia de caracteres-comandos. Cada caracter-comando es un caracter ‘R’ o un caracter ‘D’. El caracter ‘R’ se corresponde con un movimiento del robot hacia la casilla adyacente a la derecha y el caracter ‘D’ se corresponde con un movimiento del robot hacia la casilla adyacente de abajo.

Cuando el robot recibe un programa, primeramente ejecuta el primer comando, después el segundo comando, luego el tercero y así sucesivamente hasta que ejecuta el último comando del programa. Posteriormente el robot comienza a ejecutar el programa desde su inicio, tantas veces como sea necesario, hasta que el robot salga del área de juego (lo cual se considera una victoria), o hasta que arribe a una casilla peligrosa (lo cual se considera una derrota).

Hacer un programa que permita:

  • Leer desde la consola las dimensiones del área de juego, el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot y los caracteres que aparecen en cada casilla del área del juego.
  • Desarrollar un programa para el robot que le permita salir del área del juego y recopilar tantos premios como sea posible.
  • Imprimir hacia la consola la máxima cantidad de premios que le fue posible recolectar al robot con algún programa de K o menos caracteres.
En IslaGrande están diseñando un nuevo juego para dispositivos móviles. Este juego es un rompecabezas con reglas relativamente simples. El juego se desarrolla sobre un área rectangular que consiste de N filas con M columnas. Las filas están numeradas de arriba hacia abajo, comenzando por uno, las columnas en las filas están numeradas de izquierda a derecha, comenzando por uno. Cada casilla corresponde a las coordenadas (X, Y), donde X es el número de la fila y Y es el número de la columna. En la casilla de la esquina superior izquierda hay un robot, el cual en un movimiento solamente puede ir hacia la casilla adyacente de abajo o hacia la casilla adyacente a la derecha. Algunas de las casillas del área de juego son peligrosas. Si el robot alcanza una casilla peligrosa deja de funcionar y el juego se pierde. En las otras casillas hay premios. Si el robot alcanza una casilla que contiene premios, el tomará todos los premios de esa casilla. El objetivo del juego es que el robot salga de los límites del área de juego, sin pasar por una casilla peligrosa y recopile tantos premios como sea posible.

No obstante, el robot tiene una memoria limitada, así que él solamente puede almacenar en su memoria un programa consistente de a lo sumo K caracteres-comandos. Un programa es una secuencia de caracteres-comandos. Cada caracter-comando es un caracter ‘R’ o un caracter ‘D’. El caracter ‘R’ se corresponde con un movimiento del robot hacia la casilla adyacente a la derecha y el caracter ‘D’ se corresponde con un movimiento del robot hacia la casilla adyacente de abajo.

Cuando el robot recibe un programa, primeramente ejecuta el primer comando, después el segundo comando, luego el tercero y así sucesivamente hasta que ejecuta el último comando del programa. Posteriormente el robot comienza a ejecutar el programa desde su inicio, tantas veces como sea necesario, hasta que el robot salga del área de juego (lo cual se considera una victoria), o hasta que arribe a una casilla peligrosa (lo cual se considera una derrota).

Hacer un programa que permita:

  • Leer desde la consola las dimensiones del área de juego, el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot y los caracteres que aparecen en cada casilla del área del juego.
  • Desarrollar un programa para el robot que le permita salir del área del juego y recopilar tantos premios como sea posible.
  • Imprimir hacia la consola la máxima cantidad de premios que le fue posible recolectar al robot con algún programa de K o menos caracteres.
En IslaGrande están diseñando un nuevo juego para dispositivos móviles. Este juego es un rompecabezas con reglas relativamente simples. El juego se desarrolla sobre un área rectangular que consiste de N filas con M columnas. Las filas están numeradas de arriba hacia abajo, comenzando por uno, las columnas en las filas están numeradas de izquierda a derecha, comenzando por uno. Cada casilla corresponde a las coordenadas (X, Y), donde X es el número de la fila y Y es el número de la columna. En la casilla de la esquina superior izquierda hay un robot, el cual en un movimiento solamente puede ir hacia la casilla adyacente de abajo o hacia la casilla adyacente a la derecha. Algunas de las casillas del área de juego son peligrosas. Si el robot alcanza una casilla peligrosa deja de funcionar y el juego se pierde. En las otras casillas hay premios. Si el robot alcanza una casilla que contiene premios, el tomará todos los premios de esa casilla. El objetivo del juego es que el robot salga de los límites del área de juego, sin pasar por una casilla peligrosa y recopile tantos premios como sea posible.

No obstante, el robot tiene una memoria limitada, así que él solamente puede almacenar en su memoria un programa consistente de a lo sumo K caracteres-comandos. Un programa es una secuencia de caracteres-comandos. Cada caracter-comando es un caracter ‘R’ o un caracter ‘D’. El caracter ‘R’ se corresponde con un movimiento del robot hacia la casilla adyacente a la derecha y el caracter ‘D’ se corresponde con un movimiento del robot hacia la casilla adyacente de abajo.

Cuando el robot recibe un programa, primeramente ejecuta el primer comando, después el segundo comando, luego el tercero y así sucesivamente hasta que ejecuta el último comando del programa. Posteriormente el robot comienza a ejecutar el programa desde su inicio, tantas veces como sea necesario, hasta que el robot salga del área de juego (lo cual se considera una victoria), o hasta que arribe a una casilla peligrosa (lo cual se considera una derrota).

Hacer un programa que permita:

  • Leer desde la consola las dimensiones del área de juego, el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot y los caracteres que aparecen en cada casilla del área del juego.
  • Desarrollar un programa para el robot que le permita salir del área del juego y recopilar tantos premios como sea posible.
  • Imprimir hacia la consola la máxima cantidad de premios que le fue posible recolectar al robot con algún programa de K o menos caracteres.

Input specification

La entrada contiene:

Linea 1: N, M, K; la cantidad de filas del área de juego, la cantidad de columnas del área de juego y el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot.

Linea 2..N+1: en cada una de estas líneas aparecerán M caracteres, o sea, el j-ésimo caracter en la i-ésima fila describe a una casilla con coordenadas (i, j). Si el caracter es ′#′, este representa a una casilla peligrosa. De lo contrario, si el caracter es un dígito en notación decimal, representa la cantidad de premios en esa casilla. La casilla superior izquierda siempre es segura, y el número de premios en esta casilla es igual a cero.

Restricciones

    1 ≤ N ≤ 200.
    1 ≤ M ≤ 200.
    1 ≤ K ≤ 100.
La entrada contiene:

Linea 1: N, M, K; la cantidad de filas del área de juego, la cantidad de columnas del área de juego y el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot.

Linea 2..N+1: en cada una de estas líneas aparecerán M caracteres, o sea, el j-ésimo caracter en la i-ésima fila describe a una casilla con coordenadas (i, j). Si el caracter es ′#′, este representa a una casilla peligrosa. De lo contrario, si el caracter es un dígito en notación decimal, representa la cantidad de premios en esa casilla. La casilla superior izquierda siempre es segura, y el número de premios en esta casilla es igual a cero.

Restricciones

    1 ≤ N ≤ 200.
    1 ≤ M ≤ 200.
    1 ≤ K ≤ 100.
La entrada contiene:

Linea 1: N, M, K; la cantidad de filas del área de juego, la cantidad de columnas del área de juego y el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot.

Linea 2..N+1: en cada una de estas líneas aparecerán M caracteres, o sea, el j-ésimo caracter en la i-ésima fila describe a una casilla con coordenadas (i, j). Si el caracter es ′#′, este representa a una casilla peligrosa. De lo contrario, si el caracter es un dígito en notación decimal, representa la cantidad de premios en esa casilla. La casilla superior izquierda siempre es segura, y el número de premios en esta casilla es igual a cero.

Restricciones

    1 ≤ N ≤ 200.
    1 ≤ M ≤ 200.
    1 ≤ K ≤ 100.

Output specification

La salida contiene en una sola línea con un entero que es la máxima cantidad de premios que pudo recolectar.

La salida contiene en una sola línea con un entero que es la máxima cantidad de premios que pudo recolectar.

La entrada contiene:

Linea 1: N, M, K; la cantidad de filas del área de juego, la cantidad de columnas del área de juego y el número máximo de caracteres-comandos que pueden ser almacenados en la memoria del robot.

Linea 2..N+1: en cada una de estas líneas aparecerán M caracteres, o sea, el j-ésimo caracter en la i-ésima fila describe a una casilla con coordenadas (i, j). Si el caracter es ′#′, este representa a una casilla peligrosa. De lo contrario, si el caracter es un dígito en notación decimal, representa la cantidad de premios en esa casilla. La casilla superior izquierda siempre es segura, y el número de premios en esta casilla es igual a cero.

Restricciones

    1 ≤ N ≤ 200.
    1 ≤ M ≤ 200.
    1 ≤ K ≤ 100.

Sample input

3 4 3
012#
#045
6###

Sample output

12

Hint(s)

RRD: el robot comienza en la casilla (1,1), se mueve hacia la derecha hasta la casilla (1,2), de nuevo a la derecha hasta la casilla (1,3), baja hasta la casilla (2,3). Ejecutando de nuevo el programa desde el inicio el robot se mueve a la derecha hasta la casilla (2,4) y en el próximo movimiento a la derecha sale del área de juego recopilando 12 premios.

RRD: el robot comienza en la casilla (1,1), se mueve hacia la derecha hasta la casilla (1,2), de nuevo a la derecha hasta la casilla (1,3), baja hasta la casilla (2,3). Ejecutando de nuevo el programa desde el inicio el robot se mueve a la derecha hasta la casilla (2,4) y en el próximo movimiento a la derecha sale del área de juego recopilando 12 premios.

RRD: el robot comienza en la casilla (1,1), se mueve hacia la derecha hasta la casilla (1,2), de nuevo a la derecha hasta la casilla (1,3), baja hasta la casilla (2,3). Ejecutando de nuevo el programa desde el inicio el robot se mueve a la derecha hasta la casilla (2,4) y en el próximo movimiento a la derecha sale del área de juego recopilando 12 premios.

Recommendation

We have carefully selected several similar problems: 3378 | 3573 | 3599 | 3147 | 3134 | 2191