Trova la parola

Fase Territoriale 2013

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 alcuna 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

input.txt	output.txt
8 7 OLIMPIADI OLIVENT GQMPWER GTRIAYE IUICDPE AFCOIGH JKXCVRS ROMITAA STANLEE	DDBDBDBB
8 7 OLIMPIONICO OLIVENT GQMPWER GTRIAYE IUICDPE AFCOIGH JKXCVRS ROMITAA STANLE	ASSENTE

/*
	www.valcon.it
	OII 2013 - Fase territoriale - Trova la parola
*/
#include
#include
#include
using namespace std;

#define DMAX 100

char ruzzle[DMAX+1][DMAX+1];
char P[DMAX+1];
char soluzione[2*DMAX];

int R,C;
int L;

bool cerca(int r, int c, int p)
{	
	if(p == L)				 return true;		
	if(ruzzle[r] != P[p]) return false;
		
	soluzione[p]='D'; bool esito=cerca(r  ,c+1,p+1); if(esito) return true;
	soluzione[p]='B';     return cerca(r+1,c  ,p+1);
}

int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");	
	
	fin >> R >> C;
	fin >> P;
	for(int i=0; i < R; i++)
		fin >> ruzzle[i];
	L=strlen(P);
	
	if(cerca(0,0,0)) { soluzione[L-1]='\0'; fout << soluzione; }	
	else             {         		        fout << "ASSENTE"; }
	
	return 0;
}