ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Kuznetsov                      2:5030/566.13  08 Apr 2002  21:00:00
 To : Alex Erin
 Subject : Японские кроссворды
 -------------------------------------------------------------------------------- 
 

 
  AE> Собственно, subj. Возникла идея написать пpогpамму для их pешения.
  AE> По-моему, здесь это когда-то обсуждалось. Или может кто-то уже
  AE> занимался пpоблемой.
 
  Я тут писал на днях это дело... И вот чего могу посоветовать, но сразу
 предупреждаю алгоритм не оптимальный.
 
  В цикле пока не закончена картинка делаешь так:
     1) Бежишь сначала по всем строкам и на каждой строке расставляешь всеми
        возможными способами группы закрашенных (так чтобы это расположение не
        противоречило уже найденным точкам (из результата)) и ищешь пересечение
 всего этого        дела, если оно не пустое, то записываешь в результат. Дальше
 бежишь по        столбцам и делаешь то же самое...
     2) Если пробежав всё не нашел ни одной точки, то тыкаешь в любое место,
        заполняешь дальше если находится противоречие, то убираешь и тыкаешь в
        другое место.
 
  Пример
 
    1 2
    _ _
  1/_/_/
  2/_/_/
 
  Ответ должен быть
   _ _
  /*/Ж/
  /Ж/Ж/ (* - пусто, Ж - закрашено)
 
  Как работает алгоритм:
    1) Для первой строчки можно поставить /Ж/_/ а можно /_/Ж/ - пересечение = 0
    2) Перешли ко второй строчке:
          можно поставить только так: /Ж/Ж/ => записываем в результат
                                      _ _
                                     /_/_/
                                     /Ж/Ж/
    3) Строки кончились преходим к вертикалям - первая
           нужно расположить 1 точку, причем в результате уже стоит 1 точка,
           значит это она и есть
           Т.е в результат записываем
                                      _ _
                                     /*/_/
                                     /Ж/Ж/
 
    4) 2-й столбец.
         Расположить двойку можно только 1 способом, следовательно в результат
 
                                      _ _
                                     /*/Ж/
                                     /Ж/Ж/
 
    Все заполнено выходим!
 
                                 Hе понятно, если что, напиши - отвечу...
                             До свидания, Alex!
  * Origin: Ya! (2:5030/566.13)
 
 

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

Тема:    Автор:    Дата:    Японские кроссворды   Alex Erin   08 Apr 2002 01:48:41   Японские кроссворды   Anton Kuznetsov   08 Apr 2002 21:00:00