|
|
|
|
|
|
|
Вернуться
| 1 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 30 декабря 2009 г. 17:24:16 | |
|
каждое состояние можно закодировать, например, номером мультиперестановки(перестановки с повторениями), которую образуют буквы. Тогда можно будет легко узнавать номер из состояния и состояние из номера. Тогда надо всего лишь закодировать начальное состояние и конечное, и когда в обходе в ширину мы дошли до конечного сотояния, можно сразу же выводить ответ. Граф сам хранить не надо, просто пробовать менять на каждом шагу символ # с соседним.
|
|
|
| 2 Чабаненко Владислав Дмитриевич, 28 декабря 2009 г. 9:49:18 | |
|
а как проверять, что мы дошли уже до нужного состояния? не понял, насчёт хранения графа
|
|
|
| 3 Нигматуллин Нияз Габдуллазянович [СПбГУ ИТМО], 27 декабря 2009 г. 17:34:13 | |
а как рекурсией, по состояниям?
по-другому, так. Пусть у нас есть какое-то положение наших букв, тогда представим себе граф, где вершина это состояние, а ребро это переход из одного состояния до другого. Наша задача превратилась в нахождение кратчайшего пути в невзвешенном графе. найдем его обходом в ширину. Состояние можно закодировать числом, чтобы было удобно сохранять в позициях, которых мы были. Сам граф хранить явно не надо, просто для каждого состояния пробуем поменять две буквы, # и ее соседнюю.
всего состояний не больше 8! = 40320, ребер не больше 8! * 4.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
