Troba el camí (1) P10047


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • Input

    1 1   5 5
    
    3 2 
    3 3
    3 4
    3 5
    3 6
    3 7 

    Output

    8
    
  • Information
    Author
    Jordi Cortadella i Jordi Petit
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python