Кроссворд

  • 20
  • Недоступна
Нет, нам не придётся решать кроссворды. Нам нужно решить нетривиальную задачку про кроссворды. Есть двумерный массив, а в нём — слова, слова, слова. По горизонтали, по вертикали, по диагонали… Нужно найти все слова в массиве.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (295)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Brain4Real
Уровень 24, Москва
22 сентября, 15:04
Наиболее эффективно будет решить задачу через структуру Trie. Создаем структуру, запихиваем в нее искомые слова. Далее идем по массиву с помощью 2-х вложенных циклов и проверяем каждую ячейку рекурсивной функцией traverse по всем интересуемым направлениям. Массив направлений выглядит так:
int[][] dir = new int[][]{
                { 0, 1},
                { 1, 1},
                { 1, 0},
                { 1,-1},
                { 0,-1},
                {-1,-1},
                {-1, 0},
                {-1, 1}
        };
Метод traverse сначала проверяет, не вышла ли ячейка за границы кроссворда, и если не вышла, то есть ли текущая буква в trie. Если нету, то мы выходим из traverse по текущему направлению, и идем дальше. Если же буква есть в trie, то мы переходим на следующий trie, одновременно двигаясь по текущему же направлению dir, но перед этим нам нужно проверить, есть ли на текущем trie - завершенные слова (если есть, то добавляем их в результирующий список).
private static void traverse(char[][] crossword, int i, int j, Trie trie, int[] dir, int startY, int startX, List<Word> res) {
        if (       i < 0
                || j < 0
                || i >= crossword.length
                || j >= crossword[0].length
                || trie.next[crossword[i][j] - 'a'] == null) {
            return;
        }
        trie = trie.next[crossword[i][j] - 'a'];
        if (trie.words.size() > 0) {
            for (String word : trie.words) {
                res.add(new Word(word, startX, startY, j, i));
            }
        }
        traverse(crossword, i + dir[0], j + dir[1], trie, dir, startY, startX, res);
}
Что же такое trie и чем он так эффективен? Прочитать можно тут А пример реализации trie в данной задаче:
Brain4Real
Уровень 24, Москва
22 сентября, 15:14
class Trie {
    Trie[] next;
    List<String> words;

    public Trie() {
        this.next = new Trie[26];
        words = new ArrayList<>();
    }

    void add(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next[c - 'a'] == null)
                cur.next[c - 'a'] = new Trie();
            cur = cur.next[c - 'a'];
        }
        cur.words.add(word);
    }
}
papsnaz
Уровень 32, Самара, Russian Federation
16 сентября, 16:43
Вам удалось ее решить с 5 попытки. Я породил монстра 👺
Николай Данилов
Уровень 23, Москва, Russian Federation
8 сентября, 19:46
Кайфую, что решил сам за несколько часов)) логику выстраивал такую: сначала берем цикл и проходимся по всем словам, что поступили в метод. в этом цикле разбиваю слово на массив char. далее в двойном цикле ищу совпадение первого символа с массивом. каждое нахождение данного символа сначала определяю какие возможны направления от этого символа. прохожусь двойным циклом по всем направлениям сравнивая второй символ с массивом. если находиться совпадение то определяю направление движения слова и просто через цикл проверяю подходят ли оставшиеся символы в слове по этому направлению, если да то добавляю слово в arrayList.
Anonymous #3105051
Уровень 32, Ukraine
28 августа, 11:25
я сделал так что метод DetectAllWords вызывает метод класа Words который у меня встроился с 65 по 99 строкчи какое то большое решения от джава раш
milyasow
Уровень 34, Москва, Russian Federation
25 августа, 20:26
Мде... Несколько дней прокрастинировал, думая, как подойти к этой задаче и пытаясь формализовать алгоритм поиска, несколько дней писал код, пытаясь разобраться своими силами, без помощи Гугла. Путался в условиях, рекурсиях, сравнениях char с int, стирал, писал заново... В итоге решил путем введения класса Cell и метода getNeighbors, похожего на тот, что использовали в игре "Сапер". Но! Как оказалось, что это решение ищет в том числе и ломаные слова, что совсем не входит в условия задачи. :( А разрабатывать логику учета направления движения мне уже совсем не хотелось. Пришлось подсмотреть как реализован алгоритм поиска на GeeksToGeeks и написать свой на его основе, чтобы пройти валидацию. Спасибо, идем дальше.
Sergey Paleny
Уровень 27, Ставрополь, Россия
20 августа, 11:49
Классная задача!!! Метод detectAllWords уместился в строках 27-148) Правильное решение посмотрю потом, а решил я так: - нашёл первую букву заданного слова; - для каждого из направлений задал условие и искал слово (8 условий получилось). Совет - не делайте как я - не надо писать сразу код))) Сначала на бумаге определитесь с решением, напишите себе алгоритм. И ПОДПИСЫВАЙТЕ условия))) // Первое из восьми условий: ... // Второе из восьми условий: ... И поздравьте меня с окончанием CORE !!!!!!!!!!!!!!!!!!!!! Я вас всех поздравляю!!!!! УРРРАААА!!!!!!!!!!!!!!!
SergGlav
Уровень 23
31 июля, 20:59
Смотрите коммент от Юрия Галкина от 20 августа 2021, 20:25. Отличные тестовые прогоны! А в правильном решении используется GOTO: 🥳
Evgeny Maryanov
Уровень 35, Москва, Russian Federation
15 июля, 21:07
наверно самая классная задача которую встречал на JR, решал с удовольствием
Айбелив Айкенфлаев
Уровень 36, Москва, Россия
10 июля, 13:39
Навтыкал в метод detectAllWords восемь своих методов, каждый из которых проверяет одно из направлений. В итоге получилось 300 строк безошибочно работающего кода😂
comrade_b
Уровень 33, Амстердам, Нидерланды
8 июня, 21:42
Я решал с помощью отдельного метода findWord, в который передавал: 1. сам кроссворд 2. текущий Х 3. текущий У 4. искомое слово 5. текущий индекс буквы (важно для рекурсии в методе) 6. вектор формата X,Y (я передавал двумя символами), где -1<= X,Y<=1; итого 8 векторов; 7. и нулевой объект класса word. * Можно было бы создать отдельный класс, чтобы не городить такое количество параметров в метод, но я бы предпочел статические переменные класса Solution. Но поскольку по условиям задачи ими пользоваться нельзя, сделал так. Зато мое решение уместилось в 125 строк и 3976 символов против 183 строк и 6590 символов готового решения. Сам метод findWord я сделал рекурсивным. Если по вектору находится следующее совпадение, то я рекурсивно вызываю этот же метод. Например, слово "FDE" по нулевой строке 1. В методе detectAllWords я нахожу первое совпадение по нулевой букве слова FDE. У первой буквы будут координаты 0,0. 2. Вызываю метод findWord, в который передаю все вышеперечисленное. 3. По вектору 0,1 (который добавляет ноль к Х и 1 к У) иду от начальной точки направо. 4. Если следующий элемент (то есть 0,1) совпадает, вызываю рекурсию этого же метода. 5. Он проверят только 1 элемент по вектору, то есть 0,2 (х = 0+0+0, у = 0+1+1). 6. Как только я достигаю в индексе текущего элемента равенства с длиной строки минус 1, присваиваю переданному объекту класса Word конечные координаты и выхожу с рекурсии. ВАЖНОЕ ЗАМЕЧАНИЕ: В комментах ниже и в проверках ниже говорится, что слово может быть от одной буквы, но это неправда. У меня валидатор принял решение, где учитываются слова от 2 букв.
comrade_b
Уровень 33, Амстердам, Нидерланды
8 июня, 21:46
Далее спойлер