Troba el camí (1) P10047

Feu un programa que, donada una graella (infinita) amb obstacles, digui quin és el mínim nombre de moviments per anar d’una posició d’orígen a una posició de destí. Els moviments permesos són horitzontals o verticals, però no diagonals.

Per exemple, el nombre de passos per anar d’x a y en aquesta graella és 8:

. . . . . . . . . . . . 
. . . . . . y . . . . . 
. . . . . . . . . . . . 
. . . O O O O O O . . . 
. . . . . . . . . . . . 
. . x . . . . . . . . . 
. . . . . . . . . . . . 

Entrada

L’entrada comença amb la casella d’orígen. Després ve la casella de la posició de destí. A continuació ve una llista d’obstacles, és a dir, caselles per on no es pot passar. Cada casella ve definida per la seva posició: fila i columna.

Podeu suposar que hi ha uns pocs obstacles i que sempre hi ha un camí per anar de la posició d’orígen a la posició de destí.

Sortida

Escriviu el mínim nombre de moviments per anar de la posició d’orígen a la posició de destí donades sense passar per caselles amb obstacles.