Нахождение одностороннего ряда

263

09 февраля 2018, 17:48

Есть двумерный массив чаров. Мне надо найти в этом массиве определенные получившиеся "слова" в процессе. С условием, что слова могут идти только в некоторых направлениях: слева направо, сверху вниз, по диагонали вниз направо и по диагонали вверх направо. В другие стороны получившиеся слова не надо учитывать. С каждым добавлением символа в массив, мне надо узнать, получилось ли слово? Если да, то в определенной последовательности записать координаты ячеек в массив

Как реализовать данный алгоритм? Если что я это делаю для своей игры (а то будут говорить еще что для школы задачки не решаем)

У меня есть одна идея, но боюсь есть лучше, да и реализация в коде не ясна, поэтому и пишу сюда. При добавлении символа, мы знаем координату добавления. Поэтому мы можем пройтись по 4-м осям и все их "просканировать" на образования слов

Answer 1

Ну вот вам псевдокод, описывающий алгоритм:

for (int row = 0; row < rows; row++)
{
    for (int column = 0; column < columns; column++)
    {
        // Идем вправо
        строка = поле[row, column];
        int d = 1;
        while (column + d < columns)
        {
            строка = строка + поле[row, column + d];
            ПоискСтрокиВСловаре(строка);
            d++;
        }
        // Идем вниз
        // Аналогичный код, граничное условие (row + d < rows)
        // Идем по диагонали вниз
        // Аналогичный код, граничное условие (column + d < columns && row + d < rows)
        // Идем по диагонали вверх
        // Аналогичный код, граничное условие (column + d < columns && row - d >= 0)
    }
}

Дальнейшие оптимизации:

Запомнить минимальную и максимальную длину слов в словаре и выходить при ее достижении;
На текущем шаге проверять не только целиком слово, но и наличие слов, начинающихся с текущей подстроки;
Продумать эффективный способ хранения словаря (в виде дерева, возможно);
При добавлении новой буквы искать не целиком по всему полю, а только по строкам, столбцам и диагоналям, на которых лежит добавленная буква.