Я думаю, что Вы
являетесь большим поклонником настольной игры "Боггл". Не волнуйтесь,
если Вы не знакомы с ее правилами, я их Вам объясню. Боггл представляет собой 4
* 4 сетку из букв, в которой Вам следует найти как можно больше букв. Если я играю
в Боггл со своей женой (или против нее), она всегда выигрывает – проигравший
(это я) всегда должен делать работу по дому, как например выносить мусор.
Помогите мне выиграть.
Слова в Боггл
конструируются из соседних букв (по горизонтали, вертикали и диагонали), но
одна клетка может использоваться в слове только один раз. Только слова,
представленные в словаре, являются корректными.
Слова из 3 или 4
букв стоят 1 балл, слова из 5 букв стоят 2 балла, 6 букв 3 балла, 7 букв 5
балов. 8 буквенные слова стоят 11 баллов. Если Вы найдете более одного слова (я
надеюсь, что это будет так), то баллы за них суммируются.
Вход. Первая строка содержит количество слов w (1 < w < 300000) в словаре. Каждая из следующих w строк содержит одно слово. Слова содержат до 8 букв верхнего
регистра ('A' - 'Z'). После задания словаря идет пустая строка. В следующей
строке задано количество досок b (1
< b < 30) Боггл. Каждая доска
представляет собой сетку 4 × 4 букв верхнего регистра в четырех строках.
Доски Боггл между собой разделены пустой строкой.
Выход. Для каждой
доски выведите максимальную возможную сумму баллов, самое длинное слово и
количество найденных слов. Слова, встречающиеся дважды (или более раз) в одном
Боггл, считаются один раз. Если существует несколько самых длинных слов,
вывести лексикографически наименьшее. Считайте, что каждый Боггл содержит как
минимум одно корректное слово.
|
Пример
входа |
Пример
выхода |
|
5 ICPC ACM CONTEST GCPC PROGRAMM 3 ACMA APCA TOGI NEST PCMM RXAI ORCN GPCG ICPC GCPC ICPC GCPC |
8 CONTEST 4 14 PROGRAMM
4 2 GCPC 2 |
бор
Занесем словарь
в бор. Далее для каждой позиции (i, j) (1 ≤ i, j ≤ 4)
доски запустим поиск в глубину с
возвратом назад – переберем все слова длины не более 8, начинающиеся с буквы
стоящей в позиции (i, j). При этом одновременно движемся по
бору (с возвратом). Сохраняем найденные в Боггле слова из словаря и по ним
считаем требуемую статистику.
Объявим рабочие массивы:
·
пары (dx[i], dy[i]) (0 ≤ i < 8) содержат все направления движения по доске.
·
слово длины i
стоит toScore[i].
·
массив used хранит информацию о пройденных буквах на
доске.
·
в массив found накапливаем слова из словаря, найденные на
доске.
int dx[] = { 0, 0,-1,-1,-1,+1,+1,+1};
int dy[] = {-1,+1,-1, 0,+1,-1, 0,+1};
int toScore[] = {0, 0, 0, 1, 1, 2, 3, 5,
11, 11, 11, 11, 11, 11, 11, 11, 11};
bool used[4][4];
char boggle[4][5];
vector<string>
found;
Структура вершины бора. Пусть test – номер рассматриваемой доски Боггла. Переменная last в вершине бора содержит значение test, если в этой вершине заканчивается
слово из словаря. С ее помощью каждое слово из словаря будем находить в Боггле
не более одного раза.
struct item
{
int next[26];
bool leaf;
int last;
item()
{
for(size_t
i = 0; i < 26; i++) next[i] = -1;
leaf = false;
last = 100;
}
};
Объявим бор.
vector<item>
tries;
Вставка слова в бор.
void Insert(char
*s)
{
int i, v = 0;
item temp;
for (i = 0; i
< strlen(s); ++i)
{
char c =
s[i] - 'A';
if
(tries[v].next[c] == -1)
{
tries[v].next[c] = tries.size();
tries.push_back(temp);
}
v = tries[v].next[c];
}
tries[v].leaf = true;
}
Рекурсивный перебор слов. На данный момент мы находимся в
позиции (i, j) доски и в вершине v
бора. До этого с начала мы уже прошли слово cur.
void go(int
i, int j, string cur, int
v)
{
Если вышли за границу доски, то возвращаемся.
if (i < 0
|| j < 0 || i >= 4 || j >= 4) return;
Если позицию (i, j) доски уже посещали, то возвращаемся.
if
(used[i][j]) return;
Словарь содержит слова длины не более 8. Если уже накопилось
слово длины 8, то останавливаем поиск.
if
(cur.size() >= 8) return;
Отмечаем позицию (i,
j) пройденной.
used[i][j] = true;
К пройденному слову прикрепляем текущую букву.
cur = cur + boggle[i][j];
char ch =
boggle[i][j] - 'A';
Смотрим, куда в боре имеется переход по текущей букве из
вершины v.
int next =
tries[v].next[ch];
Если в боре перехода нет, то возвращаемся назад.
if (next ==
-1)
{
used[i][j] = false;
return;
}
Если вершина в боре отмечена как конечная, то найдено слово
из словаря. Им является слово cur.
Если tries[next].last уже равно tests, то повторно слово cur в массив found
заноситься не будет.
if
(tries[next].leaf && tries[next].last > tests)
{
tries[next].last = tests;
found.push_back(cur);
}
Совершаем перебор во все 8 сторон (по горизонтали, вертикали
и диагоналям).
for (int c = 0; c < 8; c++)
go(i + dx[c], j + dy[c], cur, next);
Перебор совершаем с возвратом. Уходим из позиции (i, j),
отмечаем ее как непройденную.
used[i][j] = false;
}
Основная часть программы. Читаем словарь, строим бор.
scanf("%d\n",&n);
tries.clear();
tries.resize(1);
for(i = 0; i < n; i++)
{
gets(word);
Insert(word);
}
Последовательно обрабатываем доски Боггла.
scanf("%d\n",&tests);
while(tests--)
{
Читаем доску 4 * 4.
for(i = 0; i
< 4; i++) gets(boggle[i]);
scanf("\n");
Очищаем массив найденных слов. Запускаем поиск слов из каждой
позиции.
found.clear();
for(i = 0; i
< 4; i++)
for(j = 0; j
< 4; j++)
go(i,j,"",0);
Ищем слово наибольшей длины. Среди таких слов ищем
лексикографически наименьшее слово. Стоимость слова подсчитываем в переменной score.
string best = *found.begin();
int score =
0;
for (i = 0; i
< found.size(); i++)
{
if
(best.size() < found[i].size() ||
(best.size() == found[i].size()
&& found[i] < best))
best = found[i];
score += toScore[found[i].size()];
}
Выводим ответ.
printf("%d %s
%d\n",score,best.c_str(),found.size());
}