Code: Select all
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.regex.Pattern;
import java.util.Collections;
class MainUltimo{
public static void main(String args[]) throws IOException{
MaterialePerK matPerK[]= new MaterialePerK[16];
int Adiac0 []={1,4,5};
matPerK[0]= new MaterialePerK(new CellaBoggle(0, 0),Adiac0 );
int Adiac1[]={0,4,5,6,2};
matPerK[1]= new MaterialePerK(new CellaBoggle(0, 1),Adiac1 );
int Adiac2[]={1,5,6,3,7};
matPerK[2]= new MaterialePerK(new CellaBoggle(0, 2),Adiac2 );
int Adiac3[]={2,6,7};
matPerK[3]= new MaterialePerK(new CellaBoggle(0, 3),Adiac3 );
int Adiac4[]= {0,1,5,9,8};
matPerK[4]= new MaterialePerK(new CellaBoggle(1, 0),Adiac4);
int Adiac5[]= {4,0,1,2,6,10,9,8};
matPerK[5]= new MaterialePerK(new CellaBoggle(1, 1),Adiac5 );
int Adiac6[]={5,1,2,3,7,11,10,9};
matPerK[6]= new MaterialePerK(new CellaBoggle(1, 2),Adiac6 );
int Adiac7[]={3,2,6,10,11};
matPerK[7]= new MaterialePerK(new CellaBoggle(1, 3),Adiac7 );
int Adiac8[]={4,5,9,13,12};
matPerK[8]= new MaterialePerK(new CellaBoggle(2, 0),Adiac8 );
int Adiac9[]={8,4,5,6,10,14,13,12};
matPerK[9]= new MaterialePerK(new CellaBoggle(2, 1),Adiac9);
int Adiac10[]={9,5,6,7,11,15,14,13};
matPerK[10]= new MaterialePerK(new CellaBoggle(2, 2),Adiac10);
int Adiac11[]={7,6,10,14,15};
matPerK[11]= new MaterialePerK(new CellaBoggle(2, 3),Adiac11);
int Adiac12[]={8,9,13};
matPerK[12]= new MaterialePerK(new CellaBoggle(3, 0),Adiac12);
int Adiac13[]={12,8,9,10,14};
matPerK[13]= new MaterialePerK(new CellaBoggle(3, 1),Adiac13);
int Adiac14[]={13,9,10,11,15};
matPerK[14]= new MaterialePerK(new CellaBoggle(3, 2),Adiac14);
int Adiac15[]={11,10,14};
matPerK[15]= new MaterialePerK(new CellaBoggle(3,3),Adiac15);
ContenitorePigEwu C= new ContenitorePigEwu();
GrafoBoggle Gr= new GrafoBoggle(matPerK,C);
LeggiPreparaM L= new LeggiPreparaM(Gr);
L.LeggiRigheM();
}
static class CellaBoggle {
private int Righe,Col;
public CellaBoggle(int r,int c){
Righe=r; Col=c;
}
int getRiga(){ return Righe; }
int getCol(){ return Col; }
void setRiga(int r){Righe=r; }
void setCol(int c){ Col=c; }
}
static class MaterialePerK {
private int NodiAdiacenti[];
private CellaBoggle C;
public MaterialePerK(CellaBoggle cb,int adiac[]) {
C=cb;
NodiAdiacenti= adiac;
}
CellaBoggle getCellaBoggle(){
return C; }
void setArrayAdiac(int ind,int val){
NodiAdiacenti[ind]=val;
}
int [] getArrayAdiac(){
return NodiAdiacenti;
}
}
static class LeggiPreparaM {
private GrafoBoggle Gr;
private String Riga;
private char B1[][];
private char B2[][];
private StringTokenizer st;
private BufferedReader In_Str;
LeggiPreparaM(GrafoBoggle G) {
Riga=""; B1=new char[4][4]; B2=new char[4][4]; st=null;
In_Str = new BufferedReader(new InputStreamReader(System.in)); Gr=G;
}
char[][] getB1() {
return B1;
}
char[][] getB2() {
return B2;
}
void LeggiRigheM()throws IOException{
int R; boolean cicla=true;
try{
while(true){
R=0;
while(R<4){
Riga=In_Str.readLine();
if(Riga.equals("#") ){
Gr.getContenitoreParole().stampaParoleComuni();
return ;
}
st= new StringTokenizer(Riga," ");
AssegnaRiga(B1,R,0);
AssegnaRiga(B2,R,0);
R++;
}
System.out.println();
Gr.TrovaParolePigEwu(getB1(),false);
Gr.TrovaParolePigEwu(getB2(),true);
Gr.getContenitoreParole().rimuoviVettore();
Gr.getContenitoreParole().allocaVettore();
Gr.getContenitoreParole().setCiSonoComuni(false);
}
}catch (IOException e) {
return;
}
}
void AssegnaRiga(char B[][],int R,int C1){
while(st.hasMoreTokens() && C1<4){
B[R][C1] = st.nextToken().charAt(0);
C1++;
}
return ;
}
}
static class ContenitorePigEwu {
private boolean ciSonoComuni;
private Vector<ArrayList<String>> parole = new Vector<ArrayList<String>>(26);
private ArrayList<String> paroleComuni ;
private ArrayList<String> paroleComuniPerCoppiaDiM= new ArrayList<String>();
ContenitorePigEwu(){
for(int i=0 ; i<26 ;i++){
parole.insertElementAt(new ArrayList<String>(),i);
}
ciSonoComuni=false;
paroleComuni= new ArrayList<String>();
}
public Vector<ArrayList<String>> getParole() {
return parole;
}
public ArrayList<String> getParoleComuni() {
return paroleComuni;
}
boolean ciSonoComuni(){
return ciSonoComuni;
}
void setCiSonoComuni(boolean p){
ciSonoComuni=p;
}
void rimuoviVettore(){
parole.removeAllElements();
paroleComuni.clear();
}
void allocaVettore(){
for(int i=0 ; i<26 ;i++)
parole.insertElementAt(new ArrayList<String>(),i);
paroleComuni= new ArrayList<String>();
}
void inserInOrdineParolaDatoUnaCella(String parola){
int indVett= parola.charAt(0)-65;
parole.get(indVett).add(parola);
}
void ordinaVettore(ArrayList<String> arr){
Collections.sort(arr);
}
void cercaComuni(String parola2matr){
int indVett= (parola2matr.charAt(0)-65);
if(parole.get(indVett).size()!=0){
int left, right;
left = 0;
right =parole.get(indVett).size();
while (left!=right-1) {
int m = (right+left)/2 ;
String sm = parole.get(indVett).get(m);
if(sm.compareTo(parola2matr)<0)
left = m;
else if (sm.compareTo(parola2matr)>0)
right = m;
else {
left = m;
right = m+1;
}
}
if(parola2matr.equals(parole.get(indVett).get(left) )){
paroleComuni.add(parola2matr);
ciSonoComuni=true;
}
}
}
void stampaParoleComuni(){
int k=0 ;
paroleComuniPerCoppiaDiM.remove(paroleComuniPerCoppiaDiM.size()-1);
for(; k<paroleComuniPerCoppiaDiM.size() ; k++){
if(paroleComuniPerCoppiaDiM.get(k)=="-" )
System.out.println();
if(paroleComuniPerCoppiaDiM.get(k)=="0")
System.out.println("There are no common words for this pair of boggle boards.");
else
if(paroleComuniPerCoppiaDiM.get(k)!="-")
System.out.println(paroleComuniPerCoppiaDiM.get(k));
}
}
void memorizzaParoleInComune(){
ArrayList<String> monoS = new ArrayList<String>();
for(int i=0 ;i<paroleComuni.size() ;i++){
if(!monoS.contains(paroleComuni.get(i)))
monoS.add(paroleComuni.get(i));
}
if(monoS.size()==0){
paroleComuniPerCoppiaDiM.add("0");
}
else
paroleComuniPerCoppiaDiM.addAll(monoS);
paroleComuniPerCoppiaDiM.add("-");
monoS.clear();
}
}
static class GrafoBoggle{
private HashMap<Integer,MaterialePerK> GrafoTavola =new HashMap<Integer, MaterialePerK>(16, 16) ;
private MaterialePerK matPerK[];
private ContenitorePigEwu contenitoreParole;
private boolean Decr[];
GrafoBoggle(MaterialePerK mater[],ContenitorePigEwu cp){
contenitoreParole=cp;
matPerK=mater;
for(int k=0 ;k<16 ; k++)
GrafoTavola.put(k, matPerK[k]);
Decr= new boolean[4];
}
public ContenitorePigEwu getContenitoreParole() {
return contenitoreParole;
}
void TrovaParolePigEwu(char B[][],boolean ConfrontoP){
int contaVoc=0;
int Nodo_K=0;
for(int i=0 ; i<Decr.length ;i++)
Decr[i]=false;
while(Nodo_K<16){
if(CeVocaleAlNodo(Nodo_K,B) ){
contaVoc++;
Decr[0]=true;
}
for(int i=0; i<GrafoTavola.get(Nodo_K).getArrayAdiac().length;i++) {
int Nodo_K2=GrafoTavola.get(Nodo_K).getArrayAdiac()[i];
if(Nodo_K!=Nodo_K2){
if(CeVocaleAlNodo(Nodo_K2,B)){
contaVoc++;
Decr[1]=true;
}
for(int u=0; u< GrafoTavola.get(Nodo_K2).getArrayAdiac().length; u++) {
int Nodo_K3 = GrafoTavola.get(Nodo_K2).getArrayAdiac()[u];
if(CeVocaleAlNodo(Nodo_K3,B)){
contaVoc++;
Decr[2]=true;
}
if(contaVoc<3 && Nodo_K3!=Nodo_K && Nodo_K3!= Nodo_K2 ){
for(int y=0 ; y< GrafoTavola.get(Nodo_K3).getArrayAdiac().length; y++){
int Nodo_K4= GrafoTavola.get(Nodo_K3).getArrayAdiac()[y];
if(CeVocaleAlNodo(Nodo_K4,B)) {
contaVoc++;
Decr[3]=true;
}
if(contaVoc==2 && Nodo_K4!=Nodo_K2 && Nodo_K4!=Nodo_K && Nodo_K4!=Nodo_K3){
String s = new StringBuilder().append(ConvertiNodoLettera(Nodo_K, B)).append(ConvertiNodoLettera(Nodo_K2, B)).
append(ConvertiNodoLettera(Nodo_K3, B)).append(ConvertiNodoLettera(Nodo_K4, B)).toString();
if(!ConfrontoP) {
contenitoreParole.inserInOrdineParolaDatoUnaCella(s);
}
else
contenitoreParole.cercaComuni(s);
}
if(Decr[3]){
contaVoc--;
Decr[3]=false;
}
}
}
if(Decr[2]){
contaVoc--;
Decr[2]=false;
}
}
if(Decr[1]){
contaVoc--;
Decr[1]=false;
}
}
}
if(Decr[0]){
contaVoc--;
Decr[0]=false;
}
if(!ConfrontoP){
int ind = ConvertiNodoLettera(Nodo_K, B)-65;
contenitoreParole.ordinaVettore(contenitoreParole.getParole().get(ind));
}
Nodo_K++;
}
if(ConfrontoP){
contenitoreParole.ordinaVettore(contenitoreParole.getParoleComuni() );
contenitoreParole.memorizzaParoleInComune();
}
}
char ConvertiNodoLettera(int kN,char B[][]){
CellaBoggle Cb= GrafoTavola.get(kN).getCellaBoggle();
int R=Cb.getRiga(); int C=Cb.getCol();
return B[R][C];
}
boolean CeVocaleAlNodo(int Nodo_K,char B[][]){
CellaBoggle Cb=GrafoTavola.get(Nodo_K).getCellaBoggle();
int R=Cb.getRiga(); int C=Cb.getCol();
switch( B[R][C] ){
case 'A': return true ;
case 'Y': return true;
case 'E': return true;
case 'O': return true;
case 'I': return true;
case 'U': return true;
};
return false;
}
}
}
)- I used binary search trees, but while inserting compared words with a special function.
