Реализация игры Boggle не в состоянии получить все слова

Я прочитал доску в вектор чар вектор B это доска 4х4
Прочитать «отсортированный» словарь в вектор строк
Я сканирую доску 4×4, вызываю функцию fillGoodWoods для каждой отдельной ячейки.

    int main(int argc, char *argv[])
{
if ( argc < 3 )
{
std::cout << "\n usage : ./boggle boardfile dictionaryfile ";
return 1;
}
// B is the 4x4 board
boggle::board B;
// this function reads the board fine
boggle::read_board(argv[1], B);
// read the 'sorted' dictionary into a vector
std::vector<std::string> dict;
boggle::read_dictionary(argv[2], dict);
int bsize = B.size();

std::map<std::string, unsigned int> goodwords;

for ( unsigned int i = 0; i < bsize; ++i )
{
for ( unsigned int j = 0 ; j < bsize ; ++j)
{
std::vector<std::vector<bool> > marked;
for (unsigned int z = 0; z < bsize; z++)
{
marked.push_back(std::vector<bool>(bsize, false));
}
std::string pathStr ;
pathStr += B[i][j];
marked[i][j] = true; // mark visited
fillGoodwords(i, j, goodwords, marked, pathStr, dict, B);
}
}
std::map<std::string, unsigned int>::iterator itr;for ( itr = goodwords.begin(); itr != goodwords.end(); ++itr)
{
//std::cout << itr->first << "\n";
}
return 0;
}

FillGoodWords — это DFS:
Он должен пройти через каждую соседнюю ячейку, которая еще не была посещена на пути.
С доской, которая содержит 193 слова, я могу извлечь только 80 слов

void fillGoodwords(int startrow , int startcol ,
std::map<std::string, unsigned int> &goodwords,
std::vector<std::vector<bool> > marked,
std::string currentStr,
const std::vector<std::string> &dict,
const boggle::board &B)
{
if(currentStr.find("unt") == 0) {
cout<<currentStr<<" -- ";
}

if (currentStr.length() >= 3)
{
if ( std::binary_search(dict.begin(), dict.end(), currentStr))
{
goodwords.insert(std::pair<std::string, unsigned int>(currentStr, 1));
}
}
int boardsize = B.size();
for ( int x = -1; x <= 1 ; ++x)
{
for ( int y = -1; y <= 1 ; ++y)
{
// checking if out of bounds
if (  (startrow + x) < 0 || (startcol + y) < 0 || (startrow + x) >= boardsize || (startcol + y) >= boardsize )
{
continue;
}
else if (marked[startrow + x][startcol + y] == false)
{
marked[startrow + x][startcol + y] = true; // mark visited
fillGoodwords(startrow + x , startcol + y, goodwords, marked, currentStr + B[startrow + x][startcol + y], dict, B);
}
}
}
}

0

Решение

Вы помечаете ячейку как посещенную до повторного прочтения, чтобы ее нельзя было использовать дважды в одном и том же слове. Но вы должны очистить ячейку для «родственных» путей после возвращения рекурсии:

marked[startrow + x][startcol + y] = true; // mark as visited
fillGoodwords(startrow + x , startcol + y, goodwords, marked, currentStr + B[startrow + x][startcol + y], dict, B);
marked[startrow + x][startcol + y] = false; // clear again for other paths

Проиллюстрировать:

S O C K
T P X Y
A H Z E
O W N T

Если вы начнете с S и идти на восток к O вы в конце концов найдете SOCK, Рекурсия возвращается к S и вы исследуете камеру на юг. Ты не можешь найти STOCK или же STOP, поскольку O все еще помечен как видимый.

3

Другие решения

Других решений пока нет …