所以，我试图弄清楚如何实现对 Boggle 模拟的递归调用。有两个参与者：人类和计算机。当人走时，他/她在棋盘上找到一个单词（随机洗牌），递归调用应该检查有效性。基本上，我必须遍历从单词输入的索引 0 开始的相邻字母，然后以这种方式爬行，每次检查以确保单词存在与否。问题是我不完全知道如何做到这一点。到目前为止，这是我的代码，我提供了一些伪代码来进一步解释我的意图。任何人都可以帮忙吗？
#include <iostream>
#include <cctype>
#include <cmath>
#include "strlib.h"
#include "gboggle.h"
#include "graphics.h"
#include "grid.h"
#include "lexicon.h"
#include "random.h"
#include "simpio.h"
#include "Board.h"
using namespace std;
/* Constants */
const int MIN_WORD_COUNT = 4;
const int boardSize = 16;
const int BOGGLE_WINDOW_WIDTH = 650;
const int BOGGLE_WINDOW_HEIGHT = 350;
const string STANDARD_CUBES[16] = {
"AAEEGN", "ABBJOO", "ACHOPS", "AFFKPS",
"AOOTTW", "CIMOTU", "DEILRX", "DELRVY",
"DISTTY", "EEGHNW", "EEINSU", "EHRTVW",
"EIOSST", "ELRTTY", "HIMNQU", "HLNNRZ"
};
const string BIG_BOGGLE_CUBES[25] = {
"AAAFRS", "AAEEEE", "AAFIRS", "ADENNN", "AEEEEM",
"AEEGMU", "AEGMNN", "AFIRSY", "BJKQXZ", "CCNSTW",
"CEIILT", "CEILPT", "CEIPST", "DDLNOR", "DDHNOT",
"DHHLOR", "DHLNOR", "EIIITT", "EMOTTT", "ENSSSU",
"FIPRSY", "GORRVW", "HIPRRY", "NOOTUW", "OOOTTU"
};
/* Function prototypes */
void welcome();
void giveInstructions();
void checkBoard( Vector<string> );
void shakeCubes( int, int, Vector<string> &, Grid<char> & );
void checkBoardLetters( Grid<char> );
void checkHumanWords( Set<string> );
void findHumanWordsOnBoard( Set<string> &, Grid<char> );
bool boardContainsHumanWord( Grid<char>, string );
void toupper(string& word);
bool askQuestion(string question);
void customConfiguration(int boardSize);
void shuffleBoard(int boardSize, const string cubes[]);
void humanTurn(Grid<char>& cubeLetters, Set<string> &alreadyUsedWords, Lexicon &dictionary);
/* Main program */
int main() {
initGraphics(BOGGLE_WINDOW_WIDTH, BOGGLE_WINDOW_HEIGHT);
welcome();
giveInstructions();
int rows = 4;
int cols = 4;
int boardSize = rows*cols;
Vector<string> vec;
Set<string> humanWords;
Grid<char> cubeLetters( rows, cols );
Lexicon dictionary("EnglishWords.dat");
// Task 1: Copy constant array into a vector vec
for( int i = 0; i < rows * cols; i++ )
{
vec.add( STANDARD_CUBES[ i ] );
}
string instructions = "Do you need instructions?";
if (askQuestion(instructions))
giveInstructions();
string customConfig = "Do you want a custom configuration?";
drawBoard( rows, cols );
if (askQuestion(customConfig)){
customConfiguration(boardSize);
}
else {
shakeCubes( rows, cols, vec, cubeLetters );
}
// Task 2
humanTurn( cubeLetters, humanWords, dictionary );
// debug
//checkHumanWords( humanWords );
// Task 3
findHumanWordsOnBoard( humanWords, cubeLetters );
// debug
//checkHumanWords( humanWords );
//else {
// shuffleBoard(boardSize,STANDARD_CUBES);
//}
return 0;
}
/*
* Function: shakeCubes
* Usage: shakeCubes( int, int, Vector<string> & );
* -----------------
* Randomize cubes and their sides.
*/
void shakeCubes( int rows, int cols, Vector<string> &vec, Grid<char> &cubeLetters )
{
// Shuffle cubes
srand ( time(NULL) );
random_shuffle( vec.begin(), vec.end() );
char c;
int i = 0, j = 0;
// Shuffle cube sides
foreach( string s in vec )
{
c = s[ rand() % 6 ];
labelCube( i, j, c );
cubeLetters[ i ][ j ] = c;
if( j == 3 )
{
i++;
j = 0;
}
else
j++;
}
}
void humanTurn(Grid<char>& cubeLetters, Set<string> &alreadyUsedWords, Lexicon &dictionary) {
cout << endl << "Find all the words you can."
<< endl << "Signal that you're finished by entering an empty line." << endl << endl;
do {
cout << "Enter a word: ";
string word = getLine();
if(word.empty())
break; // the only way out of the do-while loop
toupper(word);
if(word.length() < MIN_WORD_COUNT) // word < min word length
{
cout << "I'm sorry, but we have our standards." << endl
<< "That word doesn't meet the minimum word length." << endl;
}
else if(alreadyUsedWords.contains(word)) // word has already been entered
{
cout << "You've already found that word!" << endl;
}
else if( dictionary.contains( word ) ) // word not in lexicon
{
alreadyUsedWords.add(word);
recordWordForPlayer( word, HUMAN );
}
else
{
cout << "You can't make that word!" << endl;
}
} while(true);
}
/*
* Function: checkBoard
* Usage: checkBoard( Vector<string> );
* -----------------
* Print out current state of Boggle board.
*/
void checkBoard( Vector<string> vec )
{
cout << endl;
foreach(string s in vec)
{
cout << s << endl;
}
}
void checkBoardLetters( Grid<char> cubeLetters )
{
cout << endl;
for( int i = 0; i < 4; i ++ )
{
for( int j = 0; j < 4; j++ )
{
cout << cubeLetters[i][j] << endl;
}
}
}
void checkHumanWords( Set<string> humanWords )
{
cout << endl;
foreach( string s in humanWords )
{
cout << s << endl;
}
if( humanWords.isEmpty() )
cout << "human word set is empty" << endl;
}
// Does board contain word? RECURSIVE
bool boardContainsWord( Grid<char> cubeLetters, string word )
{
foreach( char c in cubeLetters )
for( int i = 0; i < cubeLetters.numRows(); i++ )
{
for( int j = 0; j < cubeLetters.numCols(); j++ )
{
if( cubeLetters[i][j] == word[0] )
{
if( word.length() == 1 )
return true;
else
return boardContainsWord( cubeLetters, word.substr(1) );
}
}
}
return false;
}
/*
bool boardContainsLetter( Grid<char> cubeLetters, char letter )
{
return false;
}
// Task 3: Reduce set of HumanWords to those that exist on board
void findHumanWordsOnBoard( Set<string> &humanWords, Grid<char> cubeLetters )
{
foreach( string word in humanWords )
{
if( !boardContainsWord( cubeLetters, word ) )
humanWords.remove( word );
}
}
*/
/* *** Brainstorming and Under Construction ***
I need to save (x,y) coordinates and store in a Set collection class to describe path.
I need a recursive, boolean function that takes in string word, Grid board, and Set path to check valid words.
This recursion will check each adjacent letter (and can start from top left [row-1][col-1], and move around the chosen letter);
It also has to check whether it's inBounds before proceeding.
/*
* Function: welcome
* Usage: welcome();
* -----------------
* Print out a cheery welcome message.
*/
void welcome() {
cout << "Welcome! You're about to play an intense game ";
cout << "of mind-numbing Boggle. The good news is that ";
cout << "you might improve your vocabulary a bit. The ";
cout << "bad news is that you're probably going to lose ";
cout << "miserably to this little dictionary-toting hunk ";
cout << "of silicon. If only YOU had a gig of RAM..." << endl << endl;
}
/*
* Function: giveInstructions
* Usage: giveInstructions();
* --------------------------
* Print out the instructions for the user.
*/
void giveInstructions() {
cout << endl;
cout << endl << "The boggle board is a grid onto which I will randomly distribute" << endl
<< "dice. These 6-sided dice have letters rather than numbers on the faces, " << endl
<< "creating a grid of letters on which you try to form words. You go first, " << endl
<< "entering the words you find that are formed by tracing adjoining " << endl
<< "letters. Two letters adjoin if they are next to each other horizontally, " << endl
<< "vertically, or diagonally. A letter can only be used once in the word. Words" << endl
<< "must be at least 4 letters long and can only be counted once. You score points" << endl
<< "based on word length, a 4-letter word is worth one, 5-letters two, etc. After your " << endl
<< "tiny brain is exhausted, I, the brilliant computer, will find all the remaining " << endl
<< "words in the puzzle and double or triple your paltry score." << endl << endl;
cout << "Hit return when you're ready...";
getLine();
}
//Function call to capitalize every letter in a string
void toupper(string& word) {
for(int i = 0; i < word.size(); i++) {
word[i] = toupper(word[i]);
}
}
// A do-while loop to keep asking for a YES/NO answer to a given question
bool askQuestion(string question) {
do {
cout << question << " ";
string answer = getLine();
if(toupper(answer[0]) == 'N') return false;
else if(toupper(answer[0]) == 'Y') return true;
} while (cout << "Please answer yes or no." << endl);
return 1;
}
// Requests user for a board configuration input for the given size board
// and labels the cubes with the corresponding input string
void customConfiguration(int boardSize) {
cout << endl << "Enter a " << boardSize
<< "-character string to identify which letters you want on the cubes."
<< endl << "The first " << sqrt(double(boardSize))
<< " letters are the cubes on the top row from left to right "
<< endl << "next " << sqrt(double(boardSize))
<< " letters are the second row, etc."
<< endl << "Enter the string: ";
string answer;
do {
answer = getLine();
if(answer.size() >= double(boardSize)) break;
} while (cout << "String must include " << boardSize
<< " characters! Try again: ");
toupper(answer);
int strIndex = 0;
for (int row = 0; row < sqrt(double(boardSize)); row++){
for (int col = 0; col < sqrt(double(boardSize)); col++){
char answerSubStr = answer[strIndex];
labelCube(row, col, answerSubStr);
strIndex++;
}
}
}