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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
| #include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <fstream>
#include <io.h>
#include <algorithm>
#include <vector>
using namespace std;
// счетчик для букв
struct WordAndCounter
{
char Char;
int Counter;
WordAndCounter(char _char = ' ', int _counter = 0)
: Char(_char), Counter(_counter) {}
};
// элементы словаря
struct ElementofVocabulary
{
string String; // слово
bool Busy; // функция, для отмечания слова флагом "занято/не занято"
struct ElementofVocabulary
(const string& str = "", bool b = false)
: String(str), Busy(b) {}
};
vector<vector<WordAndCounter> > Field;
vector<struct ElementofVocabulary> Vocabulary;
// параматры кроссворда
struct ParametresOfCrossword
{
const char VERTICAL = 'v', HORIZONTAL = 'h';
int X, Y; // расположение слова
char Dir; // направление слова(горизонтальное/вертикальное)
int Length; // длина слова
ParametresOfCrossword(int _x, int _y, int _len, char _dir)
: X(_x), Y(_y), Dir(_dir), Length(_len) {}
// горизонтальное и вертикальное смещение очередной буквы слова относительно предыдущей
int dx() { return (Dir == HORIZONTAL) ? 1 : 0; }
int dy() { return (Dir == VERTICAL) ? 1 : 0; }
};
vector<ParametresOfCrossword> Crossword; // оnисание кроссворда
// функция, сортирующая слова по длине
bool SizeofWord(const struct ElementofVocabulary& lhs, const struct ElementofVocabulary& rhs)
{
return lhs.String.length() < rhs.String.length();
}
// Функция считывает описание кроссворда из файла crossword.txt и словаря из файла vocabulary.txt
void ReadData()
{
ifstream crossw("crossword.txt"), voc("vocabulary.txt");
string temp;
// считуем все слова словаря последовательно
while (!voc.eof())
{
voc >> temp;
Vocabulary.push_back(struct ElementofVocabulary(temp, false));
}
// сортируем словарь по длине слов
sort(Vocabulary.begin(), Vocabulary.end(), SizeofWord);
// считуем описание кроссворда
int W, H, x, y, len;
char dir;
// размер поля
crossw >> W; crossw >> H;
for (;;)
{
// считуем очередной элемент описания
crossw >> x; crossw >> y;
crossw >> len; crossw >> dir;
if (crossw.eof())
break;
Crossword.push_back(ParametresOfCrossword(x, y, len, dir));
}
// заполним все поле кроссворда пустыми символами
for (int i = 0; i < W; i++)
{
vector<WordAndCounter> col(H);
fill(col.begin(), col.end(), WordAndCounter());
Field.push_back(col);
}
}
// фуекция, определяющая соответстивия букв в слове и на поле кроссворда
bool IsthisplaceforWord(ParametresOfCrossword c, const string& word)
{
for (unsigned i = 0; i < word.length(); i++)
{
// если очередная ячейка непуста и при этом символ в ней не соответствует i-му символу слова
if (Field[c.X + i*c.dx()][c.Y + i*c.dy()].Char != ' ' &&
Field[c.X + i*c.dx()][c.Y + i*c.dy()].Char != word[i])
return false; // слово нельзя разместить на данной позиции
}
return true;
}
// функция, размещающая слово в данной позиции
void PutWordinthisPlace(ParametresOfCrossword c, const string& word)
{
for (unsigned i = 0; i<word.length(); i++)
{
Field[c.X + i*c.dx()][c.Y + i*c.dy()].Char = word[i];
Field[c.X + i*c.dx()][c.Y + i*c.dy()].Counter++;
}
}
// удаления слова с позиции
void DeleteWord(ParametresOfCrossword c, const string& word)
{
for (unsigned i = 0; i < word.length(); i++)
{
if (--Field[c.X + i*c.dx()][c.Y + i*c.dy()].Counter == 0)
Field[c.X + i*c.dx()][c.Y + i*c.dy()].Char = ' ';
}
}
bool MadeCrossword(unsigned CoordNo)
{
if (CoordNo == Crossword.size())
// если подкроссворд пуст
return true;
// получить диапазон слов, длина каждого из которых равна Crossword[CoordNo].Length
pair<vector<struct ElementofVocabulary>::iterator, vector<struct ElementofVocabulary>::iterator> range =
equal_range(Vocabulary.begin(), Vocabulary.end(),
string(Crossword[CoordNo].Length, ' '), SizeofWord);
// цикл по словам словаря
for (vector<struct ElementofVocabulary>::iterator p = range.first;p != range.second; p++)
if (!p->Busy && IsthisplaceforWord(Crossword[CoordNo], p->String))
{ // если слово не занято и его можно разместить на позиции Crossword[CoordNo]
PutWordinthisPlace(Crossword[CoordNo], p->String); // разместить слово
p->Busy = true; //пометить слово флагом занято
if (MadeCrossword(CoordNo + 1)) // если подкроссворд решается
return true;
DeleteWord(Crossword[CoordNo], p->String); // удалить слово
p->Busy = false; // пометить слово флагом незанятое
}
return false;
}
int main(int argc, char* argv[])
{
setlocale(LC_ALL, "RUS");
// считать параметры кроссворда
ReadData();
if (MadeCrossword(0))
{
// если решение найдено, распечатать содержимое Field
for (unsigned y = 0; y < Field[0].size(); y++)
{
for (unsigned x = 0; x < Field.size(); x++)
cout << Field[x][y].Char;
cout << endl;
}
}
else
cout << "Введены неверные параметры в crossword.txt или добавте новые слова в vocabulary.txt";
cout << endl;
system("pause");
return 0;
} |
(
