Mapa con obstáculos P46532

Jugando a un juego de plataformas, nos encontramos en una pantalla con un mapa cuadriculado infinito. Nuestro jugador se encuentra en la casilla (x,y) y necesitamos llegar a la casilla (x′,y′). Para ello, queremos ir por un camino de distancia mínima, ya que nuestro nivel de energía es crítico. El jugador, en cada paso, puede desplazarse de la casilla donde se encuentra a una adyacente, es decir, si el jugador se encuentra en la casilla (i,j) podrá desplazarse únicamente a una de estas: (i+1,j), (i−1,j), (i,j+1), (i,j−1). Las casillas con coordenadas de la forma (2*n, 2*m), donde n y m son enteros, están bloqueadas y el jugador no puede situarse sobre ellas. Haz un programa que, dadas las coordenadas de las casillas de inicio y de final, escriba la distancia mínima que ha de recorrer el jugador.

Entrada

La entrada contiene varias líneas. En cada línea hay cuatro enteros: x, y, x′, y′, todos ellos de valor absoluto menor a 10⁸. Se te asegura que las casillas (x,y) y (x′,y′) nunca son de la forma (2*n,2*m).

Salida

Por cada línea de la entrada escribe en una línea el número mínimo de pasos necesarios para ir de la casilla inicial a la final.

Puntuación

• Test1:  50 Puntos 

  Resolver varios casos donde las casillas inicial y final siempre están en distinta fila y columna.

• Test2:  50 Puntos 

  Resolver varios casos de todo tipo.