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+C1 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 DDBDBDBB
OLIMPIADI
OLIVENT
GQMPWER
GTRIAYE
IUICDPE
AFCOIGH
JKXCVRS
ROMITAA
STANLEE
File input.txt File output.txt
8 7 ASSENTE
OLIMPIONICO
OLIVENT
GQMPWER
GTRIAYE
IUICDPE
AFCOIGH
JKXCVRS
ROMITAA
STANLEE
Basta provare ad andare a destra e a sinistra con una funzione ricorsiva, arrivati alla fine si stampano i passaggi:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<cstdlib> #include<iostream> #include<fstream> #include <string> #define M 101 #define no "ASSENTE" using namespace std; ifstream in; ofstream out; bool t=true; int r,c; string p; char g [M][M]; void cerca(int rr, int cc,string storia,int ch){ //prova a cercare la parola. Se non trova si ferma. Se trova stampa if ( ++ch == p.length()){ out<<storia; t=false; return;} if (r>rr+1 && g [rr+1][cc]==p[ch]) cerca (rr+1,cc,storia+"B",ch); if (c>cc+1 && g [rr][cc+1]==p[ch]) cerca (rr,cc+1,storia+"D",ch); return; } int main(){ in.open("input.txt"); out.open("output.txt"); in>>r>>c>>p; for (int i=0;i<r;i++) for (int j=0;j<c;j++) in>> g[i][j]; if (p[0]==g[0][0]) cerca (0,0,"",0); if (t) out<<no; return 0;} |
