Selezioni Territoriali 2013
[Difficoltà D=2]
Trova la parola (trovaparola)
Descrizione del problema
Visto il successo del gioco Ruzzle, che riprende il noto paroliere, i giochi basati su trovare parole stanno vivendo un periodo molto popolare. Luciano, patito di giochi di tutti i tipi, ha ideato un nuovo gioco, che funziona nel modo seguente: avete una griglia di caratteri e una parola da trovare nella griglia, partendo dalla cella in alto a sinistra. Le uniche mosse consentite sono gli spostamenti a destra o in basso. Ad esempio, considerate la seguente griglia e la parola “olimpiadi”:
O | L | I | V | E | N | T |
G | Q | M | P | W | E | R |
G | T | R | I | A | Y | E |
I | U | I | C | D | P | E |
A | F | C | O | I | G | H |
J | K | X | C | V | R | S |
R | O | M | I | T | A | A |
S | T | A | N | L | E | E |
In questo caso, la sequenza di spostamenti è “DDBDBDBB”, rappresentando gli spostamenti a destra con il carattere D e quelli in basso con il carattere B. Non esiste nessuna soluzione, invece, se la parola da cercare è “olimpionico”. Il vostro compito consiste nello scrivere un programma che, ricevute in ingresso una parola (da cercare) e una griglia, restituisca la sequenza di spostamenti, qualora esista una soluzione, oppure stampi “ASSENTE”. Se dovessero esistere molteplici sequenze di spostamenti corrette, è sufficiente stamparne una qualunque.
Dati di input
Il file input.txt è composto da 2+R righe. La prima riga contiene due interi positivi R e C: le dimensioni della griglia, ovvero il numero di righe R e il numero di colonne C. La riga successiva contiene P, una parola da cercare, rappresentata da una stringa lunga almeno 2 caratteri (alfabetici maiuscoli) e al massimo R+C-1 caratteri. Le rimanenti R righe del file contengono le righe della griglia, rappresentate da stringhe di C caratteri alfabetici maiuscoli.
Dati di output
Il file output.txt è composto da una sola riga contenente una stringa di testo: la sequenza di spostamenti necessari per trovare la parola nella griglia, se la parola è presente, oppure la stringa “ASSENTE” (senza le virgolette).
Assunzioni
• 2 ≤ R, C ≤ 100
Esempi di input/output
File input.txt | File output.txt |
8 7 OLIMPIADI OLIVENT GQMPWER GTRIAYE IUICDPE AFCOIGH JKXCVRS ROMITAA STANLEE | DDBDBDBB |
File input.txt | File output.txt |
8 7 OLIMPIONICO OLIVENT GQMPWER GTRIAYE IUICDPE AFCOIGH JKXCVRS ROMITAA STANLEE | ASSENTE |
Nota/e