// TPuzzle.cc // TF solution to A Puzzling Problem // ECNA 2007 #include using namespace std; const int MAX=102; struct occupied { int TheWord; occupied *next; }; char Board[MAX][MAX]; int Graph[MAX][MAX]; occupied *Overlaps[MAX][MAX]; int rows, cols, words; int visited[MAX]; //******************************************* void PrintStuff(){ /* cout<<" *** Board *** "<TheWord; ptr = ptr->next; } cout<>Board[i][j]; } //******************************************* //dispose of all nodes void CleanUp(){ occupied *ptr, *ptr2; for(int i=0;inext; delete(ptr); ptr = ptr2; } */ } } //******************************************* //directions: 'A'= NE, 'B'=SE, 'C'=SW, 'D'=NW bool Found(char w[MAX], int r, int c, char dir){ int n = strlen(w); if(dir=='E') for(int i=0; iTheWord=wordNo; ptr=Overlaps[r][c+i]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r][c+i]; Overlaps[r][c+i] = node; } else if(dir=='W') for(int i=0; iTheWord=wordNo; ptr=Overlaps[r][c-i]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r][c-i]; Overlaps[r][c-i] = node; } else if(dir=='S') for(int i=0; iTheWord=wordNo; ptr=Overlaps[r+i][c]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r+i][c]; Overlaps[r+i][c] = node; } else if(dir=='N') for(int i=0; iTheWord=wordNo; ptr=Overlaps[r-i][c]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r-i][c]; Overlaps[r-i][c] = node; } else if(dir=='A') //NE for(int i=0; iTheWord=wordNo; ptr=Overlaps[r-i][c+i]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r-i][c+i]; Overlaps[r-i][c+i] = node; } else if(dir=='B') //SE for(int i=0; iTheWord=wordNo; ptr=Overlaps[r+i][c+i]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r+i][c+i]; Overlaps[r+i][c+i] = node; } else if(dir=='C') //SW for(int i=0; iTheWord=wordNo; ptr=Overlaps[r+i][c-i]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r+i][c-i]; Overlaps[r+i][c-i] = node; } else if(dir=='D') for(int i=0; iTheWord=wordNo; ptr=Overlaps[r-i][c-i]; while(ptr!=NULL){ //make additions to GRAPH[][] w = ptr->TheWord; Graph[wordNo][w] = Graph[w][wordNo] = 1; ptr = ptr->next; } node->next = Overlaps[r-i][c-i]; Overlaps[r-i][c-i] = node; } //PrintStuff(); //PrintLinks(); cout<0) BFS(0); else BFS(1); for(int i=0;i>rows>>cols>>words; while(rows>0){ Init(); GetBoard(); for(int i=0;i>w; FindWord(w,i); } //cout<<"done"<>rows>>cols>>words; } return 0; }