Frutas y Baldosas


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Después de comer tanta fruta en la cocina del IPVCE, Dosberto está teniendo algunos sueños extraños! En su sueño más reciente, él está atrapado en un laberinto en la forma de una grilla de \(N×M\) baldosas \((1\leN,M\le1,000)\). Él comienza en la baldosa superior-izquierda y quiere llegar a la baldosa inferior-derecha. Cuando el está parado en una baldosa, pude moverse potencialmente a cualquier baldosa adyacente en cualquiera de las cuatro direcciones cardinales.

¡Pero espere! Cada baldosa tiene un color, y cada color tiene una propiedad diferente! La cabeza le duele a Dosberto simplemente de pensar en eso:

  • Si una baldosa es roja, entonces es impasable.
  • Si una baldosa es rosada, entonces se puede caminar en ella normalmente.
  • Si una baldosa es naranja, entonces se puede caminar en ella normalmente, pero dejará a Dosberto oliendo a naranjas.
  • Si una baldosa es azul, entonces contendrá pirañas que dejaran pasar a Dosberto solamente si él huele a naranjas.
  • Si una baldosa es purpura, entonces Dosberto saltará a la siguiente baldosa en esa dirección (al menos que no pueda cruzarla). Si esta baldosa también es una baldosa purpura, entonces Dosberto continuará saltando hasta que aterrice en una baldosa no purpura o se estrelle con una baldosa impasable. Saltar encima de una baldosa cuenta como un movimiento. Las baldosas purpuras también le quitan el olor a Dosberto.

(Si usted está confundido con las baldosas purpuras, el ejemplo ilustrará su uso.)

Por favor, ayude a Dosberto a llegar de la baldosa superior-izquierda a la baldosa inferior-derecha en tan pocos movimientos como sea posible.

Formato de entrada:

La primera línea tiene dos enteros N y M, representando el número de filas y de columnas del laberinto.

Cada una de las siguientes N líneas contiene M enteros, representando el laberinto:

  • El entero '0' es una baldosa roja
  • El entero '1' es una baldosa rosada
  • El entero '2' es una baldosa naranja
  • El entero '3' es una baldosa azul
  • El entero '4' es una baldosa purpura

Los enteros de la baldosa superior-izquierda e inferior-drecha siempre serán '1'.

Formato de salida

Un solo entero, representando el número mínimo de movimientos que Dosberto debe hacer para cruzar el laberinto o -1 si es imposible hacerlo.

Entrada de ejemplo:

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

Salida de ejemplo:

10

En este ejemplo, Dosberto camina un cuadrado abajo y dos cuadrados a la derecha (y luego salta un cuadrado más a la derecha). Él camina un cuadrado arriba, un cuadrado a la izquierda y un cuadrado hacia abajo (saltando dos cuadrados hacia abajo) y finaliza caminando un cuadrado más a la derecha. Esto es un total de 10 movimientos


Comments


  • 2
    victoredel  commented on March 14, 2021, 11:38 p.m.

    Undertale