[C++] Trovaparola

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                                   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;}