Обратный поиск слова ⇐ C++

[Anonymous]

Попытка сделать мою рекурсивную функцию более эффективной. Предполагается, что это должно заполнить слова в сетку в как можно больше комбинаций. Прямо сейчас он делает много вызовов в CanPlaceWord и не использует сетки, а вместо этого перезапускается. Любые решения, чтобы сделать его более эффективным, приветствуются.// Main solve function
bool solve(std::vector& grid, std::vector& words, const
std::string& solution_mode) {
const int grid_height = grid.size();
const int grid_width = grid[0].size();
bool is_grid_filled = true;

if (words.empty()) {
is_grid_filled = isGridFilled(grid);
if (!is_grid_filled) {
fillEmptyCells(grid, disclude_words, unique_solutions); // Assuming this function exists
return false;
}

// Avoid duplicate solutions early
if (is_grid_filled && !containsDiscludedWord(grid, disclude_words)) {
std::string grid_str = gridToString(grid); // Assuming this function exists
if (unique_solutions.find(grid_str) == unique_solutions.end()) {
unique_solutions[grid_str] = true;
solutions[solution_count++] = grid_str; // Assuming 'solutions' and 'solution_count' exist
if (solution_mode == "one_solution") {
return true; // Stop after finding one solution
}
}
}
return false;
}

std::string word = words.back();
words.pop_back();
bool found_solution = false;
std::string reversed_word = word;
std::reverse(reversed_word.begin(), reversed_word.end()); // Precompute reversed word

for (int reverse = 0; reverse < 2; ++reverse) {
// Select normal or reversed word
const std::string& current_word = (reverse == 0) ? word : reversed_word;

for (int x = 0; x < grid_height; ++x) {
for (int y = 0; y < grid_width; ++y) {
for (int dir_x = -1; dir_x = grid_width) {
continue;
}

if (canPlaceWord(grid, current_word, x, y, dir_x, dir_y)) {
placeWord(grid, current_word, x, y, dir_x, dir_y);
found_solution = solve(grid, words, solution_mode);
removeWord(grid, current_word, x, y, dir_x, dir_y);

if (found_solution && solution_mode == "one_solution") {
words.push_back(word);
return true; // Stop after finding one solution
}
}
}
}
}
}
}

words.push_back(word);
return found_solution;
}


Подробнее здесь: https://stackoverflow.com/questions/794 ... ord-search