25523번 - Trošak 점수다국어

Marin radi kao zaposlenik u jednoj firmi. Nedavno je otkrio kako mu vještine u natjecateljskom programiranju mogu pomoći i na novom poslu, no ne na način koji bi mnogi očekivali.

Marin i firma nalaze se u istom gradu koji predstavljamo kao $N \times M$ matricu, matricu s $N$ redaka i $M$ stupaca. Marinova kuća nalazi se na istoku (negdje u prvom stupcu), a firma se nalazi na zapadu (negdje u zadnjem stupcu). Preciznije, Marinova kuća nalazi se na polju $(A, 1)$, a firma na polju $(B, M)$.

Firma nudi opciju Putni trošak, što dulje Marin putuje od kuće do firme to će mu firma više platiti. Svaki dan po dolasku u firmu Marin predaje rutu kojom je putovao. Rutu opisujemo kao put u matrici u kojoj je dozvoljeno kretanje u četiri smjera (gore, dolje, lijevo i desno). Taj put ne smije imati cikluse odnosno ne smije se neko polje posjetiti dva puta. Također prvo polje puta mora biti Marinova kuća, a zadnje polje firma.

Marin je primjetio da su ta pravila koja je firma postavila jako blaga te je kao vrsni natjecatelj odlučio to iskoristiti u svoju korist i pronaći najdulji put koji poštuje pravila firme.

Pomozi Marinu pronaći što dulji put od kuće do firme prema danim pravilima. Put opisujemo kao niz polja, a svaka dva uzastopna polja u nizu moraju biti susjedna u matrici.

Napomena: Pažljivo promotri sekciju BODOVANJE.

U prvom su retku prirodni brojevi $N$ i $M$ ($2 ≤ N, M ≤ 100$), brojevi iz teksta zadatka.

U drugom su retku prirodni brojevi $A$ i $B$ ($1 ≤ A, B ≤ N$), brojevi iz teksta zadatka.

U prvi redak ispiši duljinu puta $K > 1$.

U sljedećih $K$ redaka ispiši po dva prirodna broja $X$ i $Y$ ($1 ≤ X ≤ N$), ($1 ≤ Y ≤ M$) koji redom opisuju polja na putu u matrici.

Prvo polje puta mora biti polje Marinove kuće, a zadnje polje firme.

Svaki primjer nosi maksimalno 5 bodova.

Ukoliko je rješenje neispravno (primjerice, uzastopna polja na putu nisu susjedna u matrici) rješenje nosi 0 bodova

Neka je $D$ duljina najduljeg mogućeg puta. Ukoliko je rješenje ispravno

• i $D = K$, rješenje nosi 5 bodova za taj primjer,
• inače ako je $D-K ≤ 2$ rješenje nosi 3 boda za taj primjer,
• inače ako je $D-K ≤ N$ rješenje nosi 2 boda za taj primjer,
• inače ono nosi 1 bod za taj primjer.

U primjerima vrijednima najviše 30 bodova vrijedit će da je $M=2$.

Opis trećeg probnog primjera: Kao što vidimo u drugom probnom primjeru najdulji mogući put je 9. Dakle $D=9$, a $K=7$. Koristeći pravila u sekciji bodovanje vidimo da je $D-K=2$. Odnosno taj bi primjer za takvo rješenje nosio 3 boda.