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

From

Andrey Dashkovsky (2:5002/46.4)

To

Sergey Gridasov

Date

2002-11-02T22:20:24Z

Area

RU.ALGORITHMS

Hello Sergey.

01 Ноя 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. На некотоpых клетках доски также есть клей. Задана таблица
 SG> |
 SG> | A[1:M,1:N], элемент котоpой pавен 0, если клетка чистая, и 1, если
 SG> |
 SG> | на ней есть клей. Написать алгоpитм, котоpый опpеделяет можно ли
 SG> |
 SG> | пеpекатить кyбик из левого дальнего (1,1) в пpавый ближний (M,N)
 SG> |
 SG> | yгол так, чтобы он нигде не пpиклеился.
 SG> | --------------------------------------------------------------------
 SG> -

Берёшь доску,делаешь из неё граф, не клетки, что с клеем, туда просто нет дуги
и решаешь дейкстрой, дуги хранить не обязательно, можно это получать динамически
во время работы программы. Небольшая проблема в том, что я так и не понял
условия приклеевания, если считать, что приклеевание только тогда когда сторона
с клеем на кубике соприкасается с клеткой доски намазанной клеем, тогда вершин
будет MxNx6, т.е. в каждой клетке ещё 6 состояний. Ну а далее смотри по
ограничениям, на m и n.

Если приклеивание на любой намазанной грани, хоть на кубике хоть на доске, в
алгоритме меняется немного, просто работать будет значительно быстрее, т.к.
меньше дуг в графе будет.

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


Andrey

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