Missatge ocult X96443

Maria i Josep han d’intercanviar sovint informació i no volen que la resta dels seus companys de despatx puguin assabentar-se. Per això han acordat un sistema simple de xifrat que amaga el missatge dins d’una matriu quadrada de lletres majúscules. Heu de fer un programa que rebi una matriu amb un missatge ocult i ho escrigui.

Per recuperar el missatge heu de seguir un recorregut (cíclic) de la matriu per diagonals i en sentit creixent (veure figura) i tenir en compte alguns paràmetres addicionals.

• ℓ el nombre de caràcters que es necessita extreure de la matriu.
• p la posició inicial de la primera lletra del missatge ocult.
• d el nombre de posicions que cal saltar (en el recorregut per diagonals) per trobar la següent lletra del missatge ocult.

A més sabem que el missatge original està format per paraules que contenen exclusivament lletres majúscules i que el blanc que separe dues paraules s’ha reescrit, abans d’ocultar-ho, amb la combinació XX.

El vostre programa ha d’utilitzar la següent definició:

struct Coord {

  int x,y;

};

i també ha de definir, implementar i utilitzar la funció:

Coord seguentD (const Coord& p, int n);

que, donades les coordenades d’una posició en una matriu quadrada n × n , calcula la posició següent d’acord amb un recorregut per diagonals en sentit creixent. Por exemple si n=8, la funció amb p=(7,7) ha de tornar les coordenades (0,0), amb p=(0,7), (7,1) i amb p=(2,1), (1,2).

Entrada

L’entrada consisteix en diverses línies contenint informació sobre matrius amb missatges ocults. La descripció d’una matriu s’inicia amb una línia amb 5 valors enters, n , d , ℓ ( d ·ℓ <n ² ) i f , c , ( p = (f, c ) amb 0 ≤ f, c <n ) que determinen els paràmetres. Seguits de n línies descrivint la matriu M que amaga el missatge per files.

Sortida

Per a cada matriu la sortida está formada pel missatge ocult, escrit amb les paraules separades per un blanc. Podeu assumir que la combinació XX mai forma part d’una paraula del missatge original, que mai apareix la combinació XXX en un missatge ocult i que el missatge ocult sempre té com a mínim una paraula.

Seguiu el format especificat en els exemples.