33 static std::vector<sCell>
find(
int pColumns,
int pRows,
const std::vector<std::string>& pLetters,
34 const std::string& pWord,
bool pSnake)
36 const std::vector<sCell> orthogonal = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
37 const std::vector<sCell> diagonal = {{1, -1}, {-1, -1}, {1, 1}, {-1, 1}};
38 std::vector<sCell> any = orthogonal;
39 any.insert(any.end(), diagonal.begin(), diagonal.end());
43 const std::vector<sCell>* mDirections;
46 std::vector<sPass> passes = {{&orthogonal,
false}, {&diagonal,
false}};
49 passes.push_back({&any,
true});
52 for (
const sPass& pass : passes)
54 for (
int row = 0; row < pRows; ++row)
56 for (
int column = 0; column < pColumns; ++column)
58 std::vector<sCell> path = pathFrom({column, row}, pColumns, pRows, pLetters, pWord, pass.mDirections, pass.mSnaking);
74 std::vector<sCell> mUntested;
79 static bool continues(
const std::string& pWord,
std::size_t pAt,
const std::string& pLetters)
81 return !pLetters.empty() && pWord.compare(pAt, pLetters.size(), pLetters) == 0;
84 static std::vector<sCell> pathFrom(
sCell pStart,
int pColumns,
int pRows,
const std::vector<std::string>& pLetters,
85 const std::string& pWord,
const std::vector<sCell>* pDirections,
bool pSnaking)
87 auto letterAt = [&](
sCell pCell) ->
const std::string& {
return pLetters[pCell.mColumn + pCell.mRow * pColumns]; };
89 if (!continues(pWord, 0, letterAt(pStart)))
94 std::vector<sStep> path = {{pStart, *pDirections, letterAt(pStart).size()}};
97 if (path.back().mUntested.empty())
103 const sCell direction = path.back().mUntested.back();
104 path.back().mUntested.pop_back();
105 const sCell next = {path.back().mCell.mColumn + direction.mColumn, path.back().mCell.mRow + direction.mRow};
106 if (next.mColumn < 0 || next.mColumn >= pColumns || next.mRow < 0 || next.mRow >= pRows)
111 const bool used = std::any_of(path.begin(), path.end(), [&](
const sStep& pStep) { return pStep.mCell == next; });
112 const std::string& letters = letterAt(next);
113 if (used || !continues(pWord, path.back().mEnd, letters))
118 const std::size_t end = path.back().mEnd + letters.size();
119 path.push_back({next, pSnaking ? *pDirections : std::vector<sCell>{direction}, end});
120 if (end == pWord.size())
122 std::vector<sCell> cells;
123 for (
const sStep& step : path)
125 cells.push_back(step.mCell);
static std::vector< sCell > find(int pColumns, int pRows, const std::vector< std::string > &pLetters, const std::string &pWord, bool pSnake)
Definition gfCLetterPath.h:33