Je ne suis pas joueur de ce genre de jeu, donc je vais sûrement avoir une approche très naïve mais ça me permettra de mieux comprendre ton problème.
Tu ne peux pas considérer que c'est la transition avec des cases type "eau" qui est coûteuse ?
Par exemple que si un déplacement coûte 1, aller sur une case "eau" coûte 2, naviguer entre des cases eau coûte 2 aussi, et en sortir coûte 2 par exemple ?