Tothom prefereix les carreteres amb pocs revolts. Un enginyer ha de dissenyar una carretera que uneixi dues ciutats amb el menor nombre de revolts possible sense importar la longitud de la carretera. Per tal de facilitar el disseny, l'enginyer va dibuixar un mapa amb els accidents naturals per on no podia passar la carretera, com poden ser muntanyes i barrancs. Va quadricular el mapa i va marcar aquests accidents naturals de color negre. La carretera només pot anar d'un quadre a un altre del mapa si tenen en comú un costat o una cantonada, i és clar, no pot passar per cap accident natural (quadre negre).

Direm que hi ha una corba a la carretera en el moment que acaba un tram recte i en comença un altre.

Cada quadre del mapa s'identifica per les seves coordenades, primer la fila i, després la columna. Les files es numeren de dalt a baix començant per la fila 0, i les columnes d'esquerra a dreta, començant també per la columna 0.

El Fitxer d'entrada serà un fitxer de text anomenat REVOLTS.IN. A la primera fila hi trobareu dos enters N i M que són el nombre de files i columnes del mapa

(1 £ N,M £ 50). En cadascuna de les N files restants hi trobareu M números, que poden ser 1 o 0. L'1 vol dir que en aquest quadre hi ha un accident natural i, per tant, no pot passar la carretera, i un 0 vol dir que sí que hi pot passar. A la següent línia del fitxer (la penúltima) trobareu les coordenades (fila, columna) de la ciutat A i a la última línia, les coordenades de la ciutat B

El fitxer de sortida serà un fitxer de text anomenat REVOLTS.OUT que haurà de contenir un nombre enter corresponent al menor número de corbes que pot tenir una carretera entre les ciutats A i B.

EXEMPLE

Al següent mapa de 7 files i 5 columnes, la ciutat A es troba al quadre (1,1) i la ciutat B al quadre (6,4). S'han posat diversos accidents naturals (els quadres negres). El menor número de trams rectes possible per anar d'A a B és 4, per tant, el menor número de corbes és 3. Una possible carretera amb 3 revolts està dibuixada sobre el mapa.

Tornar