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
|
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
std::ifstream in("crossword.in"); //reads ROWS, COLS and number of words, then reads words
std::ofstream out("crossword.out"); //outputs result
int ROWS, COLS, N, MAX = -1; //MAX is the score of the best solution so far
char** sol; //solution matrix
std::vector<std::string> words;
//outputs solution
void print()
{
for (int i = 0; i < ROWS; i++)
{
for (int j = 0; j < COLS; j++)
out << sol[i][j];
out << std::endl;
}
out << std::endl;
}
//check if word can be placed horizontally
int canPlaceHorizontal(int x, int y, int index, int l)
{
if (l <= COLS - y)
{
for (int i = 0; i < l; i++)
{
if (sol[x][y + i] != words[index][i] &&
sol[x][y + i] != '-')
return false;
}
return true;
}
return false;
}
//check if word can be placed vertically
bool canPlaceVertical(int x, int y, int index, int l)
{
if (l <= ROWS - x)
{
for (int i = 0; i < l; i++)
{
if (sol[x + i][y] != words[index][i] &&
sol[x + i][y] != '-')
return false;
}
return true;
}
return false;
}
void backt(int c, int score)
{
//if current word = number of words then we have a complete solution
if (c == N)
{
if (score > MAX)
{
out.close();
out.open("crossword.out");
print();
MAX = score;
}
}
else
{
//try every position in the matrix solution
for (int i = 0; i < ROWS; i++)
{
for (int j = 0; j < COLS; j++)
{
int add = 0;
int len = strlen(&words[c][0]);
char backtrack[20];
if (canPlaceHorizontal(i, j, c, len))
{ //place word in matrix and add score of solution
for (int l = 0; l < len; l++)
{
if (sol[i][j + l] == words[c][l])
add++;
backtrack[l] = sol[i][j + l];
sol[i][j + l] = words[c][l];
}
backt(c + 1, score + add);
for (int l = 0; l < len; l++)
sol[i][j + l] = backtrack[l];
}
else if (canPlaceVertical(i, j, c, len))
{
for (int l = 0; l < len; l++)
{
if (sol[i + l][j] == words[c][l])
add++;
backtrack[l] = sol[i + l][j];
sol[i + l][j] = words[c][l];
}
backt(c + 1, score + add);
for (int l = 0; l < len; l++)
sol[i + l][j] = backtrack[l];
}
}
}
return;
}
}
int main()
{
in >> ROWS >> COLS >> N;
std::string temp;
for (int i = 0; i < N; i++)
{
in >> temp;
words.push_back(temp);
}
sol = new char*[ROWS];
for (int i = 0; i < ROWS; i++)
sol[i] = new char[COLS];
for (int i = 0; i < ROWS; i++)
for (int j = 0; j < COLS; j++)
sol[i][j] = '-';
backt(0, 0);
}
|
