ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Eugene Kilachkoff                    2:5020/400     27 Nov 2002  11:47:40
 To : All
 Subject : венгерские кроссво  рды
 -------------------------------------------------------------------------------- 
 

 Давно уже хотел это сюда закинуть, и наконец, решился.
 Был у меня в свое время курсовой, там надо было составлять сабжи. Сделал 
 в лоб, но стало интересно, как подобные задачи решаются по уму. Что 
 скажет общественность ?
 
 Решение в лоб - это перебор в глубину с некоторой оптимизацией 
 (отсечением заведомо неправильных вариантов: одинокая клетка, две 
 одиноких клетки, etc).
 
 ps. Венгерский кроссворд - это матрица MxN, заполненная буквами, 
 образующими слова. Слово записывается начиная с некоторой клетки в 
 произвольном направлении, по ходу дела направление может меняться. 
 Двигаться по диагонали нельзя. Слова не пересекаются, т.е. одна клетка 
 принадлежит только одному слову.  Кроссворд считается составленным если 
 все клетки заполнены, хотя иногда допускается не более K свободных 
 клеток. Слов длиной <=4 не бывает. Кроме того, длины слов могут быть 
 ограничены (Lmin,Lmax).
 hint: Т.к. слова не пересекаются, можно обойтись генерацией только 
 нумерованных цепочек, в которые уже на следующем этапе вписываются слова.
 
 Пример правильного кроссворда:
 
   5 2 2 2 2 2 2
   5 3 3 3 2 2 2
   5 3 3 1 1 1 1
   5 3 3 4 1 1 1
   5 3 4 4 1 6 6
   5 4 4 4 6 6 6
   5 4 4 4 6 6 6
 
 Есть .png килобайтного размера, там стрелочки нарисованы. Hадо ?
 --- ifmail v.2.15dev5
  * Origin: home (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор