Carrers i avingudes P11225

Considereu un barri com Manhattan, on els carrers són “horitzontals” (en la direcció est-oest), i les avingudes són “verticals” (en la direcció sud-nord). Els carrers i avingudes s’etiqueten amb números a partir d’1: els carrers d’est a oest, i les avingudes de sud a nord. Així, cada cruïlla es pot identificar amb un parell $(c, a)$. Per exemple, la cruïlla més avall i més a la dreta del mapa s’identifica amb el parell $(1, 1)$.

Us trobeu a la cruïlla $(c_1, a_1)$ i heu d’anar a la cruïlla $(c_2, a_2)$. Quantes travessies haureu de caminar, si ho feu de forma òptima? Per exemple, si us trobeu a $(23, 7)$ i heu d’anar fins a $(42, 4)$, podeu primer moure-us a $(30, 7)$ amb cost 7, després anar a $(30, 4)$ amb cost 3, i finalment a $(42, 4)$ amb cost 12. El cost total és $7 + 3 + 12 = 22$. Es pot veure que aquest cost no es pot millorar.

Entrada

L’entrada consisteix en quatre línies, amb $c_1$, $a_1$, $c_2$ i $a_2$. Tots els nombres estan entre 1 i 1000.

Sortida

Escriviu una línia amb el cost mínim d’anar de la posició inicial a la final.