 поиск пути для кубика, в матрице nxn |
| Тёмный Эльф |
  24.11.2007 17:45
Сообщение
#1
|
 Влюблённый псих  Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация:  1   |
Привет! Подскажите пожалуйста с алгоритмом.
Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной). В самом начале пути эта запрещенная сторона находится сверху. Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю! Может, существует общий алгоритм нахождения этого пути? |
   |
 
|
  |
Ответов
| Rian |
26.11.2007 16:17
Сообщение
#2
|
 Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать. -------------------- Objective-C, Unity3d
|
|
|
|
Сообщений в этой теме
Тёмный Эльф поиск пути для кубика 24.11.2007 17:45
xds Решение "в лоб" - катать по всякому куби... 24.11.2007 18:33
Тёмный Эльф
Решение "в лоб" - катать по всякому куб... 24.11.2007 18:41
Lapp Да, я думала над этим. Но, по-моему, это будет вып... 25.11.2007 13:49 hardcase Решение "в лоб" - катать по всякому куб... 25.11.2007 14:35 Lapp Только сейчас обратил внимание, что тема абсолютно... 25.11.2007 14:23 xds Для n > 9 уже довольно долго.
Добавлено через ... 25.11.2007 15:21 hardcase Написал программу. Правда, на С# (паскаля нету на ... 25.11.2007 17:09 xds Для 8x8 и 9x9 тоже. 10x10 лень дожидаться :) 25.11.2007 17:41 Тёмный Эльф
:yes2: дольше чем полчаса.. (здесь то и встает в... 25.11.2007 19:21 Lapp думается мне, что задача при n>3 не имеет решен... 26.11.2007 5:19 xds AMD Duron @ 800 MHz:
n = 8 - 1,43 с;
n = 9 - 18,84... 26.11.2007 7:58 hardcase Ставлю свою софтину (C# .NET 2.0, без распараллели... 26.11.2007 13:25 Lapp После чистки очевидных несуразностей на компе Athl... 26.11.2007 15:50 hardcase А можно исходники посмотреть. Уж больно интересно... 26.11.2007 19:09 xds
После чистки очевидных несуразностей на компе Ath... 26.11.2007 17:01 hardcase Как то даже незаметно закончился расчет "в ло... 26.11.2007 21:18 Тёмный Эльф Времени ушло 7ч 25м.
Вот это да-а-а :mega_chok:
З... 26.11.2007 21:29 hardcase Судя по ответам xds'а, его программа справится... 26.11.2007 21:47 Тёмный Эльф Программа, откомпилированная на Microsoft Visual S... 26.11.2007 22:39 hardcase Программа, откомпилированная на Microsoft Visual ... 26.11.2007 23:11 Тёмный Эльф
Это какая такая программа??
Это программа xds. В... 26.11.2007 23:35 xds Вот мой оригинальный вариант (BP 7.0), только доба... 27.11.2007 7:00 spill Есть поиск в ширину:
1. Первую клетку пометить чис... 14.03.2008 13:44 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 22.06.2025 22:40 |