Глава 4
Исходники и exe-файл программы находятся ЗДЕСЬ
Код программы
//Crossword_01.cpp
#include <fstream>
#include <string>
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
//буква со счетчиком
struct CharAndCounter{
char Char;
int Counter;
CharAndCounter(char _char = ' ', int _counter = 0)
:Char (_char), Counter(_counter){}
};
//слово - элемент словаря
struct VocElement{
string String;
bool Busy; //флаг "занято/не занято"
VocElement(const string& str = "", bool b = false)
:String(str),Busy(b){}
};
vector< vector<CharAndCounter> > Field; // клеточное поле
vector<VocElement> Vocabulary; // словарь
//глобальные переменные
static const char VERTICAL = 'v', HORIZONTAL = 'h';
int W,H;//высота и ширина поля
//координаты, направление, длина, смещение
struct WordCoords{
int X, Y;
char Dir;
int Length;
WordCoords(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<WordCoords> Crossword; //координаты слова
bool Less(const VocElement& lhs, const VocElement& rhs){
return lhs.String.length() < rhs.String.length();
}
void ReadData(){
ifstream crossw("crossword.txt"), voc("vocabulary.txt");
string temp;
//считать последовательно все слова словаря
while(!voc.eof()){
voc >> temp;
Vocabulary.push_back(VocElement(temp, false));
}
//отсортировать словарь по длине слова
sort(Vocabulary.begin(), Vocabulary.end(), Less);
//считать описание кроссворда
int 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(WordCoords(x,y,len,dir));
}
//заполнить все поле пустыми символами
for(int i = 0; i < W; i++){
vector col(H);//вектор первого измерения
CharAndCounter _one(' ',0);//экземпляр структуры
fill(col.begin(), col.end(), _one);//заполняем вектор данными
Field.push_back(col);//помещаем вектор в вектор
}
}
//------------------------
bool CanPlace(WordCoords c, const string& word){
for(unsigned i = 0; i < word.length(); 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 PlaceWord(WordCoords 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 RemoveWord(WordCoords 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 Solve(unsigned CoordNo){
if(CoordNo == Crossword.size())
return true;
//получить диапазон слов, длина каждого из которых
//равна Crossword[CoordNo].Length
pair<vector<VocElement>::iterator, vector<VocElement>::iterator> range =
equal_range(Vocabulary.begin(), Vocabulary.end(),
string(Crossword[CoordNo].Length, ' '),Less);
//цикл по словам словаря
for(vector::iterator p = range.first;p != range.second;p++){
if(!p->Busy && CanPlace(Crossword[CoordNo], p->String)){
//если слово не занято
//и его можно разместить на позиции Crossword[CoordNo]
PlaceWord(Crossword[CoordNo], p->String);// разместить слово
p->Busy = true;//теперь слово занято
if(Solve(CoordNo + 1))
return true;
RemoveWord(Crossword[CoordNo], p->String);
p->Busy = false;
} //end if
}//end for
return false;
}
//----------------------
int main(int args,char* argv[]){
ReadData();
if(Solve(0)){
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 << "not solushion" << endl;
}
return 0;
}
Результат :
Результат может быть любым, в зависимости от файла входных данных.
Этот кроссворд получился при следующих
17 17
входных данных в файле crossword.txt :
7 0 5 v
6 1 5 h
9 0 5 v
4 3 9 h
11 2 5 v
10 5 5 h
13 4 9 v
12 7 5 h
12 9 5 h
15 6 5 v
10 11 5 h
11 10 5 v
4 13 9 h
9 12 5 v
7 12 5 v
6 15 5 h
5 10 5 v
2 11 5 h
3 4 9 v
0 9 5 h
0 7 5 h
1 6 5 v
2 5 5 h
5 2 5 v
Анализ
Назад |
Начало урока |
Вверх |
Вперед
Содержание
