Кроссворд

  • 20
  • Недоступна
Нет, нам не придётся решать кроссворды. Нам нужно решить нетривиальную задачку про кроссворды. Есть двумерный массив, а в нём — слова, слова, слова. По горизонтали, по вертикали, по диагонали… Нужно найти все слова в массиве.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (205)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий вы должны авторизоваться
Роман22 уровень, Санкт-Петербург
31 июля, 07:25
Мой вариант: тут Кратко о алгоритме: - Пробегаем по кроссворду, ища совпадение с первой буквой слова. - Определяем возможность расположения определенной длины искомого слова в разных направлениях в рамках кроссворда, чтобы не начинать искать там, где слово не может поместиться. Их 8 - 4 прямых и 4 диагонали. - Далее, в зависимости от направления, вызываем функцию поиска с текущего места в кроссворде. - В функции поиска искомое слово разбиваем на массив символов и идем по кроссворду в нужную сторону, попутно сравнивая символы. Если хотя бы один символ не совпал - прекращаем поиск. Если совпали все символы - добавляем в список найденное слово с нужными координатами. Алгоритм так же позволяет находить любое количество одинаковых слов, не важно пересекаются ли они друг с другом, начинаются ли в одном месте или расположены отдельно. Не нужно переживать с обратным порядком символов в слове. Из минусов: - код может показаться громоздким - возможно есть более оптимальные способы в плане количества итераций Собственно, похожий алгоритм где-то уже мелькал в коментах ранее. p.s. в коде исходный кроссворд слегка изменен
Babchenko Ilya31 уровень, Бельцы
18 июля, 06:02
Всем у кого проходит все тестирования, но валик не принимает. Удалите или закоментируйте все лишние sout из метода detectAllWords! + Некоторые пишут что если метод находит слово в кроссворде надо переходить к следующему, у меня находил все которые есть даже если повторяются, валик прошел.
SergeySH28 уровень, Москва
1 июля, 18:00
На удивление легко задачка решилась с первого раза. Прошелся по массиву в поисках первой буквы слова. Если нашел, то проверял в 8 направлениях циклами на совпадение букв слова с буквами массива. В логику заложил, что слово может повторятся несколько раз, из одной буквы слово может идти в любом направлении. Квест победил, пошел решать следующий )))
Lex Shkirida25 уровень
30 июня, 11:51
А кто графами решил покажите, где
Дмитрий22 уровень
27 июня, 23:15
Опять же надо уточнить условия: Могут ли быть однобуквенные слова, где стартовая и конечная позиции будут совпадать? (Судя по логике задачи, то минимально - двухбуквенные, но это надо уточнить!) Будут ли повторяться слова? И если будут, то надо ли "находить". Если слова зеркальные, то их выводить два раза? Ведь по сути метод-то "находит" слово из списка!
xodavit28 уровень, Москва
6 июня, 05:12
как сказал один преподаватель из Otus... тяжелая наркомания
Ivan D22 уровень
25 июля, 07:40
Каждый занимается своим делом. Одни преподают, другие программы пишут.
Дмитроченко Антон41 уровень, Санкт-Петербург
20 мая, 15:37
Одно слово может быть сразу в разных позициях? То есть в исходном crossword оно есть и по вертикали, горизонтали, диагонали? Или только однозначное вхождение? Кто решил и у кого еще валидатор работает, можете проверить?
Yuriy22 уровень
29 мая, 20:17
Доброго времени суток! Не могу сказать, по какой логике проверяет Валидатор, но, судя по своему коду (проверку прошел), одно слово действительно может быть сразу в нескольких направлениях. Специально проверил - если на вход даем одно слово, которое существует сразу в нескольких позициях, то и результат выдает такое же количество вариантов.
Mark Cain35 уровень, Львов
2 июня, 15:16
Только одно вхождение одного слова.
Евгений33 уровень, Санкт-Петербург
9 июня, 18:59
Дольше всего придумывал костыли, чтобы правильно находил слово "rr", конечный алгоритм находил 6 вариантов этого слова, так что слово может быть расположено как угодно.
AlinaAlina27 уровень, Санкт-Петербург
18 мая, 19:00
Такие задачи либо сразу решаются, либо упираешься в проблему, глаз замасливается, и на целый день!!! в общем 185 строк! всё отрабатывает отлично при любых проверках! Но 185(!), когда явно видно, где можно оптимизировать, но... на данный момент - это 8 циклов в отдельном методе - "рука-лицо"
Андрей27 уровень, Санкт-Петербург
15 мая, 12:05
Кто объяснит наличие требования отсутствия статических полей (а значит, и статических методов)? Чтобы раздуть и без того длинный код кучей повторов? Кстати, а если присутствует палиндром, он должен один раз считаться или два? Долбанная невнимательность. Сколько раз себе говорю - короткие блоки (особенно с индексами в массиве) лучше написать снова, чем копипастить и править. Ура! Пойду в коллекции. Всем удачи!
Mermaid Man25 уровень, Bikini Bottom
16 мая, 21:58
Статические методы использовать не запрещено. Я и сам так же сначала думал, но в этой задаче не использовать статические методы невозможно.
Павел Чумаков26 уровень
25 мая, 14:41
Возможно. Я побоялся - мало ли чего - и вогнал весь код в один метод. Такая портянка получилась %)
Ernest Aydinov25 уровень
14 мая, 12:47
как я проверял все направления. В нашей матрице y уменьшается вверх и х уменьшается налево представим что x и y это множители, каждый из которых могжет изменяться в диапазоне от -1 до 1 включительно. Эти множетели просто задают направления по которым мы проверяем остальные буквы. Как только нашли в основной матрице первую букву слова, допустим по координатам [n, m] начинаем проверку направлений. Направления тоже циклом прогоняем. Первое направление х = -1 и y = -1 это соответствует движению по диагонали налево и вверх. Т.е. мы ищем остальные буквы по адресу crossword[n + k*y][m +k*x], где k номер буквы проверяемого слова. Если слово не совпало итерируем следующее направление х = -1 и y = 0 это соответсвует движению по горизонтали влево. Остальные буквы ищем так же crossword[n + k*y][m +k*x] но теперь n меняться не будет так как множитель для изменений нулевой. Не уверен, что понятно описал решение, но весь метод detectAllWords вместе с закрывающими скобками занял менее 30 строк
Mermaid Man25 уровень, Bikini Bottom
16 мая, 22:03
Ого, 30 строк. Я сделал также, только направления не в цикле перебирал, соответственно, код в 4 раза больше.
Анна23 уровень, Москва
31 мая, 14:56
спасибо за идею!