|
|
|
El Laberint
Tornar
Imaginem un quadrat dividit en nxm quadradets als quals ens referirem per la seva fila i la seva columna. Dels nxm quadradets n'hi han k que estan marcats i no es poden travessar. El programa ha de trobar el camí més curt per passar de la cantonada (1,1) a la cantonada (n,m) sense passar pels quadradets marcats.
El fitxer d'entrada contindrà els valors de n i de m així com les coordenades dels k quadradets marcats. En el cas de que el camí no existeixi el fitxer de sortida contindrà un 0. En el cas de que el camí mínim no sigui únic, el fitxer de sortida contindrà un d'ells.
Exemple:
|
fitxer d'entrada 5 6 1 2 2 2 2 4 3 2 4 4 5 1 5 2 5 4 fitxer de sortida 1 1 2 1 3 1 4 1 4 2 4 3 5 3 6 3 6 4 6 5 |