2227 - Walking Among Mountains I

[dovier]

http://coj.uci.cu/24h/problem.xhtml?abb=2227

[ymondelo20]

Time limits was increased.
All submissions rejudged after that.

[humbertodiaz]

Saludos. Necesito algunas clarificaciones sobre este ejercicio. Primero, cual es el origen del mapa?

Segundo, la descripcion dice "always traveling forward or down with length 1". Entonces, los caminos solo pueden ser en unas direcciones particulares? Cuales direcciones son "forward" y "down"? En realidad eso no parece ser consistente con el origen que podria inferir. Quizas es un error en una traduccion y es legal moverse en cualquier direccion.

[Dariel]

primera pregunta sobre "...forward and down..." quiere decir que solo solo pudes caminar hacia delante o hacia abajo.
Sobre el origen del mapa, el punto de partida siempre es en la posición (1, 1) y el de llegada es en la posición (x, y).
Quiero decir que desde la posición (1, 1) puedes ir directamente a las posiciones (1, 2) o (2, 1).
Saludos, y espero que sea de tu ayuda.
Dariel.

[humbertodiaz]

Gracias Dariel. Entiendo lo que significan las palabras literalmente, pero con respecto al mapa, que es "adelante"? Y que es para abajo? La ambigüedad solo empeora si consideramos que el ejercicio se trata de montañas y que podemos subir o bajar (dependiendo de las alturas), que no debe ser a lo que se refiere esa parte de la descripcion. En adicion, el ejercicio dice que comenzamos en (1, 1), pero no dice cual lugar del mapa corresponde a ese punto.

[HaZard]

Gracias Dariel. Entiendo lo que significan las palabras literalmente, pero con respecto al mapa, que es "adelante"? Y que es para abajo? La ambigüedad solo empeora si consideramos que el ejercicio se trata de montañas y que podemos subir o bajar (dependiendo de las alturas), que no debe ser a lo que se refiere esa parte de la descripcion. En adicion, el ejercicio dice que comenzamos en (1, 1), pero no dice cual lugar del mapa corresponde a ese punto.

Hace ya algun tiempo que hice el ejercicio este y no me acuerdo bien, pero por lo que veo te puedes mover en las cuatro direcciones, arriba, abajo, derecha e izquierda, la casilla (1, 1) es la de más arriba a la izquierda, ahora realmente debes darte cuenta de que solo hay que analizar moverse hacia la derecha o hacia abajo, porque de lo contrario o gastas más calorías o caminas por gusto, Saludos

[humbertodiaz]

Hace ya algun tiempo que hice el ejercicio este y no me acuerdo bien, pero por lo que veo te puedes mover en las cuatro direcciones, arriba, abajo, derecha e izquierda, la casilla (1, 1) es la de más arriba a la izquierda, ahora realmente debes darte cuenta de que solo hay que analizar moverse hacia la derecha o hacia abajo, porque de lo contrario o gastas más calorías o caminas por gusto, Saludos

Gracias! Ahora lo puedo intentar. Creo que si es critico saber si uno se puede mover en las cuatro direcciones. Se pueden crear mapas en que existe una ruta que requiere movimiento en todas direcciones pero tiene el costo minimo. Por ejemplo, el siguiente mapa:

55555
99995
55555
59999
55555

...con el objetivo de llegar a la esquina de abajo a la derecha. Se puede hacer consumiendo 0 calorias si se sigue la ruta con la misma altura.

[HaZard]

Hace ya algun tiempo que hice el ejercicio este y no me acuerdo bien, pero por lo que veo te puedes mover en las cuatro direcciones, arriba, abajo, derecha e izquierda, la casilla (1, 1) es la de más arriba a la izquierda, ahora realmente debes darte cuenta de que solo hay que analizar moverse hacia la derecha o hacia abajo, porque de lo contrario o gastas más calorías o caminas por gusto, Saludos

Gracias! Ahora lo puedo intentar. Creo que si es critico saber si uno se puede mover en las cuatro direcciones. Se pueden crear mapas en que existe una ruta que requiere movimiento en todas direcciones pero tiene el costo minimo. Por ejemplo, el siguiente mapa:

55555
99995
55555
59999
55555

...con el objetivo de llegar a la esquina de abajo a la derecha. Se puede hacer consumiendo 0 calorias si se sigue la ruta con la misma altura.

Si, tienes toda la razon, no creo que ese tipo de casos de prueba aparezcan en el ejercicio, porque casi todas las soluciones son similares a la mía, aunque no estoy muy de acuerdo con que no haya casos como esos en los que hay que usar Teoría de Grafos o un Backtracking

[humbertodiaz]

Si, tienes toda la razon, no creo que ese tipo de casos de prueba aparezcan en el ejercicio, porque casi todas las soluciones son similares a la mía, aunque no estoy muy de acuerdo con que no haya casos como esos en los que hay que usar Teoría de Grafos o un Backtracking

Yo le enviare un correo a Yonny despues a ver si el sabria decir definitivamente cual era la intencion de este ejercicio. Si se permite movimiento en todas direcciones, entonces se pueden añadir pruebas que incluyan ese aspecto. No seria la primera vez que se haga una cosa asi. Yo encontre que algunas de las soluciones para Words (#1167) generaban resultados suboptimos pero todavia eran aceptadas. Se podia ver a traves de Datagen. Tambien Marko Schutz noto, usando Datagen, que las pruebas para Network Problem (#1368) no eran suficientemente fuertes y sometio algunos casos adicionales. Eso invalido muchas soluciones incorrectas, incluyendo la mia. =P