1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134 | /********************************************************************
*
* File: gfCLetterPath.h
*
* Purpose: Finds a word laid out in a grid of letter tiles - engine
* free, so it can be tested alone
*
*********************************************************************/
#ifndef gfCLetterPathhdr
#define gfCLetterPathhdr
#include <algorithm>
#include <string>
#include <vector>
// A tile can hold more than one letter ("qu"). Cells are (column, row).
class gfCLetterPath
{
public:
struct sCell
{
int mColumn;
int mRow;
bool operator==(const sCell& pRHS) const { return mColumn == pRHS.mColumn && mRow == pRHS.mRow; }
};
// pLetters holds each tile's letters, row by row. Straight lines are tried first, then, if pSnake,
// a path turning in any of eight directions. No tile is used twice. Empty if the word isn't there.
static std::vector<sCell> find(int pColumns, int pRows, const std::vector<std::string>& pLetters,
const std::string& pWord, bool pSnake)
{
const std::vector<sCell> orthogonal = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const std::vector<sCell> diagonal = {{1, -1}, {-1, -1}, {1, 1}, {-1, 1}};
std::vector<sCell> any = orthogonal;
any.insert(any.end(), diagonal.begin(), diagonal.end());
struct sPass
{
const std::vector<sCell>* mDirections;
bool mSnaking;
};
std::vector<sPass> passes = {{&orthogonal, false}, {&diagonal, false}};
if (pSnake)
{
passes.push_back({&any, true});
}
for (const sPass& pass : passes)
{
for (int row = 0; row < pRows; ++row)
{
for (int column = 0; column < pColumns; ++column)
{
std::vector<sCell> path = pathFrom({column, row}, pColumns, pRows, pLetters, pWord, pass.mDirections, pass.mSnaking);
if (!path.empty())
{
return path;
}
}
}
}
return {};
}
private:
struct sStep
{
sCell mCell;<--- Member variable 'sStep::mCell' has no initializer. [+]Member variable 'sStep::mCell' has no initializer. Member variables of native types, pointers, or references are left uninitialized when the class is instantiated. That may cause bugs or undefined behavior.
std::vector<sCell> mUntested;
// How much of the word the path covers up to and including this tile.
std::size_t mEnd;<--- Member variable 'sStep::mEnd' has no initializer. [+]Member variable 'sStep::mEnd' has no initializer. Member variables of native types, pointers, or references are left uninitialized when the class is instantiated. That may cause bugs or undefined behavior.
};
static bool continues(const std::string& pWord, std::size_t pAt, const std::string& pLetters)
{
return !pLetters.empty() && pWord.compare(pAt, pLetters.size(), pLetters) == 0;
}
static std::vector<sCell> pathFrom(sCell pStart, int pColumns, int pRows, const std::vector<std::string>& pLetters,
const std::string& pWord, const std::vector<sCell>* pDirections, bool pSnaking)
{
auto letterAt = [&](sCell pCell) -> const std::string& { return pLetters[pCell.mColumn + pCell.mRow * pColumns]; };
if (!continues(pWord, 0, letterAt(pStart)))
{
return {};
}
std::vector<sStep> path = {{pStart, *pDirections, letterAt(pStart).size()}};
while (!path.empty())
{
if (path.back().mUntested.empty())
{
path.pop_back();
continue;
}
const sCell direction = path.back().mUntested.back();
path.back().mUntested.pop_back();
const sCell next = {path.back().mCell.mColumn + direction.mColumn, path.back().mCell.mRow + direction.mRow};
if (next.mColumn < 0 || next.mColumn >= pColumns || next.mRow < 0 || next.mRow >= pRows)
{
continue;
}
const bool used = std::any_of(path.begin(), path.end(), [&](const sStep& pStep) { return pStep.mCell == next; });
const std::string& letters = letterAt(next);
if (used || !continues(pWord, path.back().mEnd, letters))
{
continue;
}
const std::size_t end = path.back().mEnd + letters.size();
path.push_back({next, pSnaking ? *pDirections : std::vector<sCell>{direction}, end});
if (end == pWord.size())
{
std::vector<sCell> cells;
for (const sStep& step : path)
{
cells.push_back(step.mCell);<--- Consider using std::transform algorithm instead of a raw loop.
}
return cells;
}
}
return {};
}
};
#endif
|