Problème E : Mots Croisés II
Fichier d’entrée : cross.in
Fichier de sortie : cross.out(IN+OUT)
Source : cross.c | cross.cpp | cross.java | cross.cs | cross.php
Il apparait que notre histoire avec les mots croisés ne va pas finir de si tôt J , cette fois-ci votre mission est un peu plus difficile que la dernière fois.
Votre mission est de remplir une grille des mots croisés en se basant sur une liste des mots sans savoir la position de ces mots !
Rappel sur le principe des mots croisés :
- Trouver le mot qui correspond à l’indication citée.
- Un mot contient au moins deux caractères.
- Il y a des indications pour les mots des lignes et des colonnes.
- Chaque ligne/colonne peut contenir un/plusieurs mots, ou ne peut contenir que des lettres/séparateurs.
Format d’entrée
Votre programme va être testé par plusieurs cas de tests, chaque cas de test est décrit comme suit :
- La première ligne contient trois entiers L C et W.
L : le nombre des lignes (strictement entre 0 et 50)
C : le nombre des colonnes (strictement entre 0 et 50)
W : le nombre des mots (strictement entre 0 et 1000)
- L lignes décrivant la grille : chaque ligne contient C caractères, le caractère ‘.’ Signifie une case vide, le caractère ‘#’ équivalent à une case qui ne reçoit pas de caractère.
- La dernière ligne contient les W mots séparés par un ou plusieurs espaces.
Format de sortie
Pour chaque cas de test :
- Afficher la grille selon le format suivant :
L lignes: chaque ligne contiendra C caractère, les caractères sont séparés par un seul espace. Si une case est vide (Noire) représenter la par le caractère ‘#’ (aucun espaces supplémentaire n’est toléré à la fin des lignes).les grilles proposés n’admettent qu’une seul solution.
- Une ligne vide
Exemple de fichiers entrée/sortie :
| cross.in | cross.out |
| 4 5 10
….. ..#.. ….# #…. he stood no ones else so she tell do lost 2 3 3 … .#. soi su it |
stood
he#no else# #lost
soi u#t |
NB : voici la grille qui correspond au premier exemple
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.regex.*;
public class cross{
public static void main(String[] args) throws FileNotFoundException{
Scanner in=new Scanner(new File(« cross.in »));
PrintWriter out=new PrintWriter(« cross.out »);
int l=0 , c=0, w=0 , i=0 , j=0;
while(in.hasNextLine()){
String ligne=in.nextLine();
String[] nombre=new String[3];
Pattern p=Pattern.compile(« \\s+ »);
Pattern p1=Pattern.compile(« # »);
nombre=p.split(ligne);
l=Integer.valueOf(nombre[0]);
c=Integer.valueOf(nombre[1]);
w=Integer.valueOf(nombre[2]);
String[] lignehor = new String[50];
for(i=0 ; i<l ; i++)
lignehor[i]=in.nextLine();
String[] mot=new String[1000];
ligne=in.nextLine();
mot=p.split(ligne);
char[][] matrice = new char[50][50];
for(i=0 ; i<l ; i++)
lignehor[i].getChars(0,c,matrice[i],0);
char[][] transmatrice = new char[50][50];
for(i=0 ; i<c ; i++)
for(j=0 ; j<l ; j++)
transmatrice[i][j] = matrice[j][i];
String[] lignevert = new String[50];
for(i=0 ; i<c ; i++){
lignevert[i] = new String(transmatrice[i]);
lignevert[i]=lignevert[i].trim();
}
String[][] mothor = new String[50][50];
String[][] motvert = new String[50][50];
for(i=0 ; i<l ; i++)
mothor[i]=p1.split(lignehor[i]);
for(i=0 ; i<c ; i++)
motvert[i]=p1.split(lignevert[i]);
String[][] posmothor=new String[50][25];
for(i=0 ; i<l ; i++){
int q=0;
for(j=0 ; j<c ; j++){
if((j==0 && matrice[i][j]=='.') || (matrice[i][j]=='.' && matrice[i][j-1]=='#')){
posmothor[i][j]=mothor[i][q];
q++;
}
else if(j==0 && matrice[i][j]=='#'){
posmothor[i][j+1]=mothor[i][q];
q++;
}
}
}
String[][] posmotvert=new String[50][25];
for(i=0 ; i<c ; i++){
int qt=0 ;
for(j=0 ; j<l ; j++){
if((j==0 && transmatrice[i][j]=='.') || (transmatrice[i][j]=='.' && transmatrice[i][j-1]=='#')){
posmotvert[i][j]=motvert[i][qt] ;
qt++ ;
}
else if(j==0 && transmatrice[i][j]=='#'){
posmotvert[i][j+1]=motvert[i][qt] ;
qt++ ;
}
}
}
for(i=0 ; i<l ; i++){
for(j=0 ; j1){
while(r<w){
if(posmotvert[j][i].length()==mot[r].length()){
stest[s]=mot[r] ;
s++ ;
}
r++;
}
for(k=i ; k<l ; k++){
if(posmothor[k][j]!=null){
t=0;
while(t<s){
r=0;
while(r1 && posmothor[k][j].indexOf(‘.’)==-1){
int m=0;
r=0;
s=0;
t=0;
trouve=false;
for(m=j ; m<c ; m++){
while(r<w){
if(posmotvert[m][k].length()==mot[r].length() && mot[r].equals(posmothor[k][j])==false && mot[r].charAt(0)==posmothor[k][j].charAt(m)){
posmotvert[m][k]=mot[r];
trouve=true;
break;
}
if(trouve){
trouve=false;
break;
}
r++;
}
}
}
if(posmothor[i][j]!=null && posmothor[i][j].length()==1){
int n=i;
while(posmotvert[j][n]==null){n–;}
posmothor[i][j]=posmotvert[j][n].substring(i,i+1);
}
}
}
for(i=0 ; i<l ; i++){
for(j=0 ; j<c ; j++){
if(matrice[i][j]=='#')
out.print('#');
else if(posmothor[i][j]!=null){
out.print(posmothor[i][j]);
}
}
out.println(" ") ;
}
out.println(" ") ;
}
in.close();
out.close();
}
}