In un campo di dimensioni 8×8 un robot si muove come il cavallo nel giuoco degli scacchi; gli sono vietate, però, le mosse nelle direzioni della rosa dei venti comprese nella seguente lista [oso,sso,sse,ese], cioè le mosse del robot in questo problema si riducono a quelle illustrate (col simbolo ♘) nella seguente figura.
Nel campo di gara le caselle della seguente lista sono interdette al robot: [[3,1],[4,4],[4,5],[4,8],[5,2],[5,3],[7,4],[7,5]].
N.B. Un elemento della lista descrive una casella indicandone le coordinate a partire dallo spigolo in basso a sinistra del campo di gara.
Inoltre, in certe caselle sono presenti dei premi, descritti dalla seguente lista: [[3,2,5],[1,3,6],[2,5,7],[4,6,8],[5,5,9]].
N.B. Un elemento della lista ha la forma: [<ascissa>,<ordinata>,<premio>].
Partendo dalla casella [1,1], il robot deve raggiungere la casella [8,8], senza passare più di una volta per una stessa casella.
Trovare:
- la lista L1 del percorso in cui si raccoglie il minor numero di premi;
- la lista L2 del percorso in cui si raccoglie il maggior numero di premi.
DISCUSSIONE
Il campo di gara
e i percorsi possibili
con premi 20, 20, 19, 26.
Risposte
- L1 = [[1,1],[3,2],[1,3],[3,4],[4,6],[6,7],[8,8]] (premio=19)
- L2 = [[1,1],[3,2],[1,3],[2,5],[4,6],[6,7],[8,8]] (premio=26)