Вот вам и кyбик...

From

Andrey Dashkovsky (2:5002/46.4)

To

Sergey Gridasov

Date

2002-11-05T17:29:27Z

Area

RU.ALGORITHMS

Hello Sergey.

03 Ноя 02 19:05, you wrote to me:


 AD>> ...
 AD>> Беpёшь доскy,делаешь из неё гpаф...

 SG> Я с гpафами не сильно дpyжy -> подкиньте, please, ссылки, где пpо них
 SG> можно поподpобнее yзнать.

Насчёт ссылок - сейчас затруднительно, а на пальцах - граф состоит из точек и
соединяющих их дуг, храница чаще всего матрицей смежности, но не всегда, т.е.
a(i,j) - вес дуги если она есть из точки i в точку j, в твоём случае все веса 1

Также в твоём случае достаточно хранить некую дрёгую структуру, и вычислять
наличие дуги в функцие, для экономия памяти, а дуга будет только в том случае
если точки(клетки) смежние и состояния кубика в них не позволяют ему
приклеиться, т.е. для каждой клетки 6 точек(вершин графа), в каждой из этих
вершин положение грани кубика с клеем различное, плюс для каждой клетки ты
отдельно хранишь с клеем она или нет.

 AD>> ...
 AD>> Небольшая пpоблема в том, что я так и не понял yсловия
 AD>> пpиклеевания...

 SG> Пpиклеивание не пpоисходит только тогда, когда гpань и клетка чистые.

понял.

 AD>> ...
 AD>> И когда вес дyги 1, я обычно использyю небольшyю модификацию
 AD>> дейкстpы, котоpая как выяснилось завётся волновым алгоpитмом.

 SG> Можно поподpобнее насчёт волнового алгоpитма, please.

Берёшь массив на кол-во вершин графа, это будет mxnx6 вершин, загоняешь в них
например -1, а в исходную 0, далее

p=true
while p do
begin
  p=false;k=0
  пробегаешь все вершины и для i-ой каждой, путь в которой k:
    пробегаешь все смежные j-ые, и если есть дуга i->j и в j путь -1, тогда:
      begin
       p=true
       и пометку ставишь путь в j = путь в i+1
      end
  k=k+1
end

Сам путь собирается в обратном порядке:
Берёшь последнюю вершину j, если там -1 значит до неё пути нету, иначе:
пробегаешь все смежные i-ые и если дуга i->j, причём путь i+1=путь j, тогда
предыдущая вершина j, и тек до тех пор, пока не доберёшься до начала.

зы: если кто этот алгоритм знает как-то иначе, меня не пинать, до этого я сам
доходил

зы2: при проходе смежных рекомендуется упростить этот шаг, т.к. если тупо
перебрать все с проверкой есть ли дуга или нет - тогда будут жуткие тормоза.

Надеюсь доходчиво рассказал.

Andrey

... Человеку свойственно ошибаться, но с помощью компьютера это удается лучше.
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)