Problem E
Planetbacke

I en inte alltför avlägsen framtid har forskare upptäckt inte bara en tidigare okänd planet här i vårt egna solsystem (se uppgiften Planet X) utan nu ytterligare en, kallad planet Y.

Forskarna är intresserade av hur topografin på Planet Y ser ut, och har lyckats mäta detta med stor noggrannhet. Vi representerar ytan som ett $N \times M$ rutnät, där varje ruta har en uppmätt höjd mellan $0$ och $9$.

Till mångas glädje visar det sig att planet Y har perfekt klimat för skidåkning (som du säkert förstår finns det inte längre någon snö på jorden vid det här laget). Skriv ett program som beräknar den längsta skidbacke som kan byggas på planet Y.

Figure 1: Till vänster visas första exemplet och till höger det andra exemplet. Det tjocka strecket visar skidbackens sträckning och de skuggade rutorna är de rutor som ingår i skidbacken.

Kravet på en skidbacke är att det ska vara en sammanhängande sekvens av rutor där varje par av rutor gränsar till varandra antingen via en gemensam sida eller ett gemensamt hörn (se figurerna ovan), och där varje ruta i sekvensen inte har högre höjd än den föregående. Det är alltså i princip tillåtet att alla rutor i skidbacken har samma höjd. Samma ruta får inte användas flera gånger men skidbacken skulle ändå kunna korsa sig själv genom ett hörn som i det andra exemplet nedan.

Indata

På den första raden står två heltal $1 \le N,M \le 7$, antalet rader och kolumner i rutnätet. Därefter följer $N$ rader med $M$ tecken på varje. Det $j$:te tecknet på rad $i$ är en siffra mellan $0$ och $9$ som motsvarar höjden för rutan. Det finns aldrig fler än $7$ rutor i rutnätet som har samma höjd.

Utdata

Programmet ska skriva ut ett heltal: det största antalet rutor som kan ingå i en godkänd skidbacke.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

3 4
1323
2301
3415

8