compiti compiti compiti..

come compiti di queste piccole vacanze di carnevale il prof ci ha chiesto di risolvere alcuni problemi che sono stati dati alle olimpiadi di informatica..ecco una delle tracce:

Mappa antica
Difficoltà D = 2.

Topolino è in missione per accompagnare una spedizione archeologica che segue un'antica mappa acquisita di recente dal museo di Topolinia. Raggiunta la località dove dovrebbe trovarsi un prezioso e raro reperto archeologico, Topolino si imbatte in un labirinto che ha la forma di una gigantesca scacchiera quadrata di NxN lastroni di marmo.
Nella mappa, sia le righe che le colonne del labirinto sono numerate da 1 a N. Il lastrone che si trova nella posizione corrispondente alla riga r e alla colonna c viene identificato mediante la coppia di interi (r, c). I lastroni segnalati da una crocetta '+' sulla mappa contengono un trabocchetto mortale e sono quindi da evitare, mentre i rimanenti sono innocui e segnalati da un asterisco '*'.
Topolino deve partire dal lastrone in posizione (1, 1) e raggiungere il lastrone in posizione (N, N), entrambi innocui. Può passare da un lastrone a un altro soltanto se questi condividono un lato o uno spigolo (quindi può procedere in direzione orizzontale, verticale o diagonale ma non saltare) e, ovviamente, questi lastroni devono essere innocui.
Tuttavia, le insidie non sono finite qui: per poter attraversare incolume il labirinto, Topolino deve calpestare il minor numero possibile di lastroni innocui (e ovviamente nessun lastrone con trabocchetto). Aiutate Topolino a calcolare tale numero minimo.