스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
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 × 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.
(그림은 원문 저장소에서 볼 수 있습니다)
Figur 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 ≤ N,M ≤ 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.
| Fall | Poängvärde | Gränser |
| 1 | 20 | 1 ≤ M, N ≤ 3 |
| 2 | 20 | Inga angränsande rutor har samma höjd. |
| 3 | 20 | Varje ruta gränsar till högst två rutor med samma höjd som sig själv. |
| 4 | 40 | Inga ytterligare begränsningar. |
예제
예제 1
3 4 1323 2301 3415
8