Ogni nodo di una griglia rettangolare mxn e’ marcato con un
intero positivo chiamato peso.

Il costo di un percorso che attraversa la griglia e’ uguale
alla somma dei pesi dei nodi toccati.

Dovendo andare dall’angolo in basso a sinistra all’angolo in
alto a destra del nostro rettangolo, e’ evidente che, se
tutti i nodi hanno lo stesso peso, i costi dei percorsi
minimi (cioe’ senza tornare indietro) sarebbero tutti
uguali. Ad es:

           B
 2  2  2  2
 2  2  2  2
 2  2  2  2
A

In questo rettangolo 3×4 i 10 percorsi minimi (5 passi) che
vanno da A a B, hanno tutti un costo = 12.

Come e’ possibile marcare i nodi di una griglia mxn con pesi
non tutti uguali, in modo tale che tutti i percorsi minimi
abbiano lo stesso costo ?