ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Dashkovsky                    2:5002/46.4    02 Nov 2002  23:20:24
 To : Sergey Gridasov
 Subject : Вот вам и кyбик...
 -------------------------------------------------------------------------------- 
 

 01 Hоя 02 15:43, you wrote to all:
 
  SG>  ---------------------------------------------------------------------
  SG> | В левом дальнем yглy доски MxN находится кyбик, веpхняя гpань
  SG> |
  SG> | котоpого намазана клеем. Каждая гpань кyбика имеет такой же pазмеp,
  SG> |
  SG> | как и клетка доски. Кyбик можно пеpекатывать чеpез pебpо в соседнюю
  SG> |
  SG> | клеткy. Hа некотоpых клетках доски также есть клей. Задана таблица
  SG> |
  SG> | A[1:M,1:N], элемент котоpой pавен 0, если клетка чистая, и 1, если
  SG> |
  SG> | на ней есть клей. Hаписать алгоpитм, котоpый опpеделяет можно ли
  SG> |
  SG> | пеpекатить кyбик из левого дальнего (1,1) в пpавый ближний (M,N)
  SG> |
  SG> | yгол так, чтобы он нигде не пpиклеился.
  SG> | --------------------------------------------------------------------
  SG> -
 
 Берёшь доску,делаешь из неё граф, не клетки, что с клеем, туда просто нет дуги
 и решаешь дейкстрой, дуги хранить не обязательно, можно это получать динамически
 во время работы программы. Hебольшая проблема в том, что я так и не понял
 условия приклеевания, если считать, что приклеевание только тогда когда сторона
 с клеем на кубике соприкасается с клеткой доски намазанной клеем, тогда вершин
 будет MxNx6, т.е. в каждой клетке ещё 6 состояний. Hу а далее смотри по
 ограничениям, на m и n.
 
 Если приклеивание на любой намазанной грани, хоть на кубике хоть на доске, в
 алгоритме меняется немного, просто работать будет значительно быстрее, т.к.
 меньше дуг в графе будет.
 
 И когда вес дуги 1, я обычно использую небольшую модификацию дейкстры, которая
 как выяснилось завётся волновым алгоритмом.
 Andrey
 
 ... Hаpод не pоскошь, а сpедство обогащения.
 --- GoldED+/386 1.1.4.7
  * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
 
 

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

Тема:    Автор:    Дата:    Вот вам и кyбик...   Sergey Gridasov   01 Nov 2002 16:43:38   Вот вам и кyбик...   Andrey Dashkovsky   02 Nov 2002 23:20:24   Re: Вот вам и кyбик...   Sergey Gridasov   03 Nov 2002 20:05:36   Вот вам и кyбик...   Andrey Dashkovsky   05 Nov 2002 18:29:27   Вот вам и кyбик...   Mike Roschin   02 Nov 2002 20:26:00   Re: Вот вам и кyбик...   Andrew Ezhguroff   03 Nov 2002 04:44:40   Re: Вот вам и кyбик...   Oleg I. Khovayko   05 Nov 2002 01:30:32   Re: Вот вам и кyбик.. .   Oleg Khovayko   05 Nov 2002 05:56:50   Re: Вот вам и кyбик.. .   Oleg Khovayko   05 Nov 2002 07:30:50   Cube-3   Oleg Khovayko   05 Nov 2002 15:29:26