PROBLEMA

Siete imprigionati in una delle città sotterranee della Cappadocia. Muovendovi nel buio per cercare di uscire, trovate per caso una mappa della città. Sfortunatamente, sulla mappa non è indicato il punto in cui vi trovate. Il vostro compito è scoprirlo esplorando la città.

La mappa della città è una griglia rettangolare costituita da quadrati unitari: ogni quadrato è o un quadrato aperto, indicato dalla lettera 'O', o fa parte di un muro, ed è indicato con la lettera 'W'. Sulla mappa è indicata la direzione del nord. Fortunatamente avete una bussola e quindi potete orientare correttamente la mappa. Inizialmente vi trovate su un quadrato aperto.

Tutto inizia chiamando la procedura (o funzione) start senza argomenti. Dovete esplorare la città usando le procedure (o funzioni) look e move. 

Potete porre domande sottoforma di una chiamata alla procedura (o funzione)look(dir) dove dir indica la direzione in cui state guardando, che può essere uno dei caratteri ‘N’, ‘S’, ‘E’ e ‘W’ che significano rispettivamente nord, sud, est e ovest. Assumente ad esempio che l'argomento dir sia ‘N’. La risposta sarà il carattere ‘O’ se il quadrato che si trova al vostro nord è aperto, e  ‘W’ se invece si tratta di un muro. In modo simile si può indagare sulle altre direzioni. 

Potete spostarvi in una delle (al più) quattro celle adiacenti chiamando move(dir) dove dir indica come sempre la direzione in cui volete muovervi, come descritto sopra. Potete spostarvi solo verso un quadrato aperto: il tentativo di spostarvi verso un muro viene considerato un grave errore. E' possibile raggiungere qualunque quadrato aperto a partire da qualunque altro quadrato aperto.

Vi viene richiesto di determinare la posizione del quadrato aperto dove avete trovato la mappa, usando il minimo numero di chiamate alla funzione 
look(dir)). Una volta determinata la posizione, la dovete riportare invocando la procedura finish(x,y) dove x è la coordinata orizzontale (ovest-est) e y la coordinata verticale (sud-nord) della posizione. 
 
 

ASSUNZIONI

• 31 <= U <=100 dove U è la larghezza della mappa, cioè il numero di quadrati nella direzione orizzontale  (ovest-est). 
• 31 <=V <=100 dove V è l'altezza della mappa, cioè il numero di quadrati nella direzione verticale (sud-nord). 
• La città è interamente circondata da mura (indicate sulla mappa). 
• L'angolo sud-ovest ha coordinate (1,1) e l'angolo nord-est ha coordinate (U,V).. 

Il file di input contenente la mappa si chiama under.inp. 

• La prima riga contiene due numeri: U, V. 

Ciascuna delle seguenti V righe corrisponde a una riga della mappa in direzione orizzontale. Ogni riga contiene U caratteri, cosicché l'x-esimo carattere sulla (V-y+2)-esima riga del file contiene informazioni relative alla posizione (x,y) sulla mappa: tale carattere può essere un muro (indicato dalla lettera ‘W’) o un quadrato aperto (indicato dalla lettera ‘O’). [Al contrario dei dati numerici, questi dati non contengono spazi bianchi.]

Non deve essere generato alcun file di output. Il risultato trovato dal programma deve essere riportato invocando la funzione finish(x,y).
 
 

ESEMPIO (Una possibile interazione che termina con una chiamata corretta alla funzione finish)

ISTRUZIONI PER I PROGRAMMATORI PASCAL

Il vostro file sorgente deve contenere:

uses undertpu.tpu; 

Questa tpu fornisce le seguenti funzioni e procedure: 

procedure start; { deve essere chiamata prima di ogni altra funzione della libreria }

function look (dir:char):char; 

procedure move (dir:char);

procedure finish (x,y:integer); { deve essere chiamata alla fine }
 
 

ISTRUZIONI PER I PROGRAMMATORI C/C++

Il vostro file sorgente deve contenere:

#include "under.h"

Includete under.obj nel progetto. La libreria fornisce le seguenti funzioni:

void start (void); /* deve essere chiamata prima di ogni altra funzione della libreria */

char look (char);

void move (char);

void finish (int,int); /* deve essere chiamata alla fine */
 
 

Create anche un progetto di nome under che deve includere il vostro programma (under.c o under.cpp) e la libreria di interazione chiamata underobj.obj. Per fare questo usate il menu project e scegliete l'opzione open per creare un progetto; quindi usate add item per includere il vostro file sorgente (under.c o under.cpp) e il file underobj.obj. 

Usate il modello LARGE per la compilazione. (Attenzione: questa è un'eccezione rispetto alle regole indicate nelle Rules of Contest.) 
 
 

VALUTAZIONE

Il vostro programma dovrà terminare entro 5 secondi.

Per ottenere un punteggio pieno, il numero di chiamate alla funzione look deve essere lo stesso o inferiore al numero di chiamate effettuate dal programma di valutazione. Potete ottenere un punteggio parziale secondo la seguente formula:

Per ottenere un punteggio pieno, A, per uno degli input di test, il numero di chiamata alla funzione look, diciamo x, deve essere lo stesso o inferiore al numero, M, indicato dal programma di valutazione. Ovviamente M è scelto in modo che sia più grande (>) del minimo numero necessario di chiamate. In particulare, M è indipendente dall'ordine (orario o antiorario) delle chiamate alla funzione. Potete ottenere un punteggio parziale se il numero di chiamate a  look è maggiore di (>) M ma minore del (<) doppio di  M. I punti in questo caso sono calcolati arrotondando all'intero più vicino il valore ottenuto dalla seguente formula:

A se x <= M

A (2M – x) /M se M < x < 2M

0 se x ³ 2M

Se il vostro programma assume comportamenti illegali, il punteggio assegnato sarà 0. I comportamenti illegali per questo problema sono:

• Il tentativo di invocare una funzione o procedura con un argomento non lecito, per esempio con un carattere che non denota nessuna direzione. 
• Il tentativo di spostarsi verso un muro. 
• La mancata aderenza alle istruzioni. 

Create un file di nome place.txt che contenga la posizione sulla mappa. Lanciate il programma. Guardate il contenuto del file result.txt.

Il file place.txt deve avere una sola riga contenente le coordinate orizzontale e verticale della posizione. Dovete inoltre creare voi stessi il file contenente la mappa under.inp. Il file result.txt conterrà due righe. La prima indica gli argomenti  x e y con cui avete invocato finish (x,y). La seconda riga contiene un messaggio della forma "You used look nnn times" indicante quante volte avete usato la funzione look. Notate che questa prova indica solo che il vostro programma è compatibile con la libreria, e non ha niente a che vedere con la correttezza della vostra soluzione.
 
 

TEMPI

Il vostro programma deve terminare l'esecuzione entro 5 secondi.

Idea dell'algoritmo

All'inizio, ovviamente, tutte le celle libere sono candidate.
Dato l'insieme delle celle candidate, la funzione muri calcola quante delle candidate hanno un muro a nord, sud, est e ovest. Se c'è almeno una direzione in corrispondenza della quale alcune celle candidate hanno un muro e altre no, scegliamo di guardare in quella direzione (più precisamente: nella direzione in corrispondenza della quale si può discriminare meglio: cioè quella in cui il numero di celle che hanno un muro e il numero di celle che non ce l'hanno sono il più vicini possibili).

Ogni volta che guardiamo in una direzione, l'insieme delle celle candidate si riduce (procedura screma). Ovviamente potremmo arrivare ad una situazione in cui non è ulteriormente possibile discriminare: in tal caso ci spostiamo sulla griglia, usando un approccio depth-first (profondità).

Per evitare i cicli, usiamo due tecniche:

• in primo luogo, evitiamo di tornare immediatamente indietro nella direzione da cui proveniamo;
• in secondo luogo, manteniamo il numero di candidate (dopo la scrematura) per la posizione corrente; se torniamo in una stessa posizione con lo stesso numero di candidate, questo implica che anche l'insieme è lo stesso e quindi dobbiamo tagliare la visita. Questi dati sono, per velocità, mantenuti in un albero di ricerca (ordinato per x e y lessicograficamente crescenti).