0
그래서 Boggle 시뮬레이션을 위해 재귀 호출을 구현하는 방법을 알아 내려고하고 있습니다. 인간과 컴퓨터의 두 선수가 있습니다. 인간이 간다면 보드에서 단어가 발견되고 (임의로 섞인), 재귀 호출은 유효성을 검사하기로되어 있습니다. 기본적으로 단어 입력의 인덱스 0에서 시작하여 인접한 문자를 반복해야하고, 그 방법으로 크롤링하고 매번 단어가 존재하는지 여부를 확인해야합니다. 문제는 정확히 어떻게하는지 모르겠습니다. 여기까지 제 코드가 있으며, 제 의도를 더 설명하기 위해 의사 코드를 제공했습니다. 누구든지 도와 줄 수 있습니까?Boggle - 재귀 구현
#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++;
}
}
}
감사합니다. :) 실제로 재귀 적으로해야했습니다. 해결책은 흥미 롭습니다. 나는 bool 플래그 그리드를 사용하여 컴퓨터 재귀를 도와야했다. –