| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > максимальное количество шагов конем |
| Автор: en-horror 5.10.2004, 20:31 |
| народ вот мне задали задание высчитать максимальное количество ходов конем на шахматной доске размерами x y. Может посоветуете каким способом это можно сделать. |
| Автор: Fantasist 5.10.2004, 21:12 |
| Обычно я такие задачи решаю методом волнового заполнения. Выбираешь начальное поле и помечаешь его нулем. Потом все поля куда может пойти конь с этого поля помечаешь единицей. Потом проходишь по всем полям с единицей и помечаешь все поля куда может пойти конь с этих полей двойками. И так далее до полного заполнения - так получишь максимальное число ходов с определенной клетки. |
| Автор: en-horror 5.10.2004, 21:35 |
| Мда это идейка!!! Надо попробовать |
| Автор: S.A.P. 5.10.2004, 22:05 |
Есть метод проще, он работает с ограниченным количеством клеток (максимум 64x64 где то так  ). Просто всегда выбираешь следующий ход, от которого есть наименьшее количество вариантов последующих ходов.Вроде понятно объяснил  . |
| Автор: en-horror 5.10.2004, 22:09 |
 |
| Автор: Alex101 8.10.2004, 14:28 | ||
Не всегда, просто сначала пытаешься пойти в такую клетку. Эта задача решается только полным перебором. Волновой алгоритм здесь не прокатит. Расставили мы единицы, а дальше? Надо хранить все варианты где-то. Все придет к тому же перебору, но еще париться с хранением... Проще рекурсия. Пусть доска D[N][N], Стоимость хранить в C[N][N]. Тогда порядок действий такой: Заполним матрицу C (сколько вариантов хода можно выбрать из каждой клетки). D заполнили нулями. Выбираем клетку D[i][j], где С[i][j]=min, D[i][j]=1, в матрице C изменили стоимость клеток (в клетку D[i][j] уже хода нет) 1. Выберем все варианты хода из D[i][j], расположим их в порядке возрастания стоимости Если ходов нет и D[i][j]=N*N то задача решена (или запоминаем max значение) Иначе Если ходы есть { Перебираем все варианты (по возрастанию стоимости) { Выбрали очередной ход в (i1,j1) Уменьшили стоимости в C Перешли к 1. } Вот примерно так, думаю, идея понятна |
| Автор: LSD 8.10.2004, 15:45 |
| Для проверки можете использовать следующий факт: стандартную шахматную доску можно полностью обойти конем, не заходя в клетку дважды. И такой способ не один. |
| Автор: Akina 8.10.2004, 16:04 |
| Существует строгое доказательство того, что прямоугольную доску M*N (M>3, N>3) можно всю обойти конем, побывав в каждой клетке по разу. |
| Автор: III.nfo 22.10.2004, 07:39 |
| А так: 12333321 23444432 34555543 34555543 34555543 34555543 23444432 12333321 точка - n ходов - n точек - n ходов итог 1 - 2 - 1*4= 4 - 2* 4= 8 2 - 3 - 2*4= 8 - 3* 8= 24 3 - 4 - 5*4=20 - 4*20= 80 4 - 6 - 4*4=16 - 6*16= 96 5 - 8 - 4*4=16 - 8*16=128 ------------------------------------------------- Итог 64 - 336 |