OPS > Movimento di un robot

di

PREMESSA

In un foglio a quadretti è disegnato un “campo di gara”, per esempio di 14 quadretti in orizzontale e 5 in verticale (vedi figura).

Ogni casella può essere individuata da due numeri (interi); per esempio la casella contenente P è individuata da essere nella sesta colonna (da sinistra) e nella terza riga (dal basso): brevemente si dice che ha coordinate [6,3]; la prima coordinata (in questo caso 6) si dice ascissa e la seconda (in questo caso 3) si dice ordinata. Le coordinate della casella contenente S sono [10,4] e di quella contenente la freccia sono [1,1]. La freccia può essere pensata come un robot, in questo caso rivolto verso destra; lo stato del robot può quindi essere individuato da tre “valori”: due per le coordinate della casella che occupa e uno per indicare il suo orientamento. Per quest’ultimo si possono usare i simboli della stella dei venti: E, S, W, N: per indicare che il robot è rivolto, rispettivamente, a destra, in basso, a sinistra, in alto (con riferimento a chi guarda il foglio); lo stato del robot, rappresentato dalla freccia nella figura è [1,1,E].

Il robot può eseguire tre tipi di comandi:

  • girarsi di 90 gradi in senso orario: comando o;
  • girarsi di 90 gradi in senso antiorario: comando a;
  • avanzare di una casella (nel senso della freccia, mantenendo l’orientamento): comando f.

Questi comandi possono essere concatenati in sequenze in modo da permettere al robot di compiere vari percorsi; per esempio la sequenza di comandi descritta dalla lista [f,f,f,f,f,a,f,f] fa spostare il robot dalla posizione e orientamento iniziali mostrati in figura fino alla casella P; le caselle via via occupate (quella di partenza e quella di arrivo comprese) sono quelle della lista:

[[1,1],[2,1],[3,1],[4,1],[5,1],[6,1],[6,2],[6,3]].

Stessa casella di arrivo si raggiunge con la lista di comandi [a,f,f,o,f,f,f,f,f], ma il percorso è diverso ed è descritto dalla lista

[[1,1],[1,2],[1,3],[2,3],[3,3],[4,3],[5,3],[6,3]].

Inoltre, nel primo caso l’orientamento finale del robot è verso l’alto (stato [6,3,N]), mentre nel secondo caso l’orientamento finale è verso destra (stato [6,3,E]).

In un foglio a quadretti è disegnato un campo di gara, per esempio di dimensioni 14×5 (cioè 14 quadretti in orizzontale e 5 in verticale, vedi figura).

Ogni casella può essere individuata da due numeri (interi); per esempio la casella contenente la lettera P è individuata spostandosi di cinque colonne da sinistra e di tre righe dal basso: brevemente si dice che ha coordinate [5,3]; la prima coordinata (in questo caso 5) si dice ascissa e la seconda (in questo caso 3) si dice ordinata. Le coordinate della casella contenente la lettera S sono [10,4] e di quella contenente il robot sono [1,1].

Il campo di gara può contenere caselle, segnate da un quadrato nero nella prima figura, interdette al robot: cioè il robot non può essere collocato in quelle caselle (che quindi si comportano come se fossero occupate da un pezzo dello stesso colore del cavallo, nel gioco degli scacchi); quindi, tenuto conto anche dei bordi del campo di gara, la mobilità del robot può essere limitata; ad esempio se il robot si trovasse nella casella in cui c’è Q si potrebbe spostare solo in 3 caselle: non può andare in [5,4] perché è interdetta; se fosse nella casella in cui c’è P avrebbe 7 mosse possibili; dalla casella [1,1] ha solo 2 mosse possibili: in [2,3] e in [3,2].

In alcuni casi il robot può spostarsi solo in una delle caselle contenenti il cavallo come illustrato nella seguente figura (allo stesso modo del cavallo nel gioco degli scacchi).

Un percorso è descritto dalla lista delle coordinate delle caselle attraversate; un possibile percorso da P (coordinate [5,3]) a Q (coordinate [3,5]) è descritto dalla lista [[5,3],[3,2],[5,1],[4,3],[3,5]].

In alcune caselle sono posti dei premi che il robot può raccogliere lungo un percorso. Ogni premio è descritto fornendo le coordinate della casella che lo contiene e il valore del premio: i premi riportati nella prima figura sono descritti dalla seguente lista [[3,2,3],[4,3,7],[3,4,5]].
Nel percorso da P a Q, sopra descritto, il totale di premi raccolti è pari a 10.

PROBLEMA 1

In un campo di gara, sufficientemente ampio, il robot (come descritto nella prima parte della premessa) è nella casella [8,8] con orientamento verso l’alto; deve eseguire il percorso descritto dalla seguente lista di comandi: [f,f,o,f,f,a,f,f,f,o,f].

Trovare l’ascissa X e l’ordinata Y della casella in cui finisce il percorso del robot.

PROBLEMA 2

In un campo di gara il robot (come descritto nella prima parte della premessa) è nella casella [9,9] con orientamento verso sinistra: trovare la lista L dei comandi da assegnare al robot per fargli compiere il percorso descritto dalla seguente lista di caselle: [[9,9],[8,9],[7,9],[6,9],[6,8],[6,7],[6,6],[6,5]].

PROBLEMA 3

Un campo di gara (come descritto nella seconda parte della premessa) ha dimensioni 5×5;

  • le caselle interdette descritte dalla seguente lista: [[1,2],[1,3],[1,4],[2,4],[3,4],[4,1],[4,2],[4,4],[4,5],[5,4]];
  • i premi, invece, sono descritti dalla seguente lista: [[3,1,10],[2,2,12],[2,3,13]].

Al robot sono vietati i movimenti corrispondenti alle direzioni della rosa dei venti indicate nella seguente lista [oso,nno,ene], cioè le mosse del robot in questo problema si riducono a quelle illustrate (col cavallo) nella seguente figura.

Partendo dalla casella [1,1], il robot deve raggiungere la casella [5,5], senza passare più di una volta per una stessa casella.

Trovare:

  • il percorso L1 in cui si raccoglie il massimo di premi;
  • il percorso L2 in cui si raccoglie il minimo di premi;
  • il numero N di percorsi possibili da [1,1] a [5,5].

PROBLEMA 4

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:

  1. la lista L1 del percorso in cui si raccoglie il minor numero di premi;
  2. la lista L2 del percorso in cui si raccoglie il maggior numero di premi.

Quesito n . 15 delle Olimpiadi di Informatica 2017 – Fase scolastica

In un campo di gara il robot si trova nella casella (13,29) con direzione verso l’alto e deve eseguire la seguente lista di comandi [f,a,f,a,f,o,f,a,f,a,f,f,a,f,f,o].

Trovare le coordinate [X,Y] della casella in cui ha termine il percorso.

In un campo di gara il robot si trova nella casella [21,19) con direzione verso il basso e deve eseguire la
seguente lista di comandi [f,a,f,f,o,f,a,f,a,f,f,a,f,f,f,o].

Trovare le coordinate [X,Y] della casella in cui ha termine il percorso.

Il robot si trova nella casella [20,20] con direzione verso sinistra (ovest) e deve eseguire il seguente percorso [(20,20),(19,20),(18,20),(18,21),(19,21),(19,20),(19,19),(18,19)].

Trovare la lista L dei comandi da assegnare al robot.

Il robot si trova nella casella [20,20] con direzione verso destra (est) e deve eseguire la seguente lista di comandi [f,f,o,f,o,f,o,f,f,o,f,a,f,f,o,f,f].

Trovare le coordinate [X,Y] della casella in cui ha termine il percorso.