Labyrintti

• Time limit: 1.00 s
• Memory limit: 128 MB

Uolevi ja Maija ovat eksyneet outoon spiraalin muotoiseen labyrinttiin. Miten he voisivat löytää taas toistensa luokse?

Labyrintti on äärettömän suuri ruudukko, jonka jokainen ruutu on lattiaa tai seinää. Suurin osa labyrintista on lattiaa. Ruudussa (0,0) on seinää, samoin 2 ruutua siitä oikealle, 4 ruutua ylöspäin, 8 ruutua vasemmalle, 16 ruutua alaspäin, 32 ruutua oikealle jne. eteenpäin 2:n potensseja.

Uolevi ja Maija voivat liikkua ruudukossa vaaka- ja pystysuuntaisesti. Tehtäväsi on laskea, mikä on pienin määrä askelia, joilla Uolevi pääsee Maijan luokse.

Syöte

Syöte sisältää neljä kokonaislukua $y_1$, $x_1$, $y_2$ ja $x_2$. Uolevi on aluksi kohdassa $(y_1,x_1)$ ja Maija on aluksi kohdassa $(y_2,x_2)$.

Koordinaatit kasvavat oikealle ja alaspäin.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: pienin askelten määrä.

Esimerkki

Syöte:
-2 -4 -3 -8

Tuloste:
29

Esimerkkiä vastaa seuraava kuva:

Osatehtävä 1 (12 pistettä)

• $-10 \le y_1,x_1,y_2,x_2 \le 10$
  

Osatehtävä 2 (29 pistettä)

• $-500 \le y_1,x_1,y_2,x_2 \le 500$
  

Osatehtävä 3 (59 pistettä)

• $-10^{15} \le y_1,x_1,y_2,x_2 \le 10^{15}$