народ вот мне задали задание высчитать максимальное количество ходов конем на шахматной доске размерами x y. Может посоветуете каким способом это можно сделать.

Обычно я такие задачи решаю методом волнового заполнения. Выбираешь начальное поле и помечаешь его нулем. Потом все поля куда может пойти конь с этого поля помечаешь единицей. Потом проходишь по всем полям с единицей и помечаешь все поля куда может пойти конь с этих полей двойками. И так далее до полного заполнения - так получишь максимальное число ходов с определенной клетки.

Мда это идейка!!! Надо попробовать

Есть метод проще, он работает с ограниченным количеством клеток (максимум 64x64 где то так ). Просто всегда выбираешь следующий ход, от которого есть наименьшее количество вариантов последующих ходов.


Вроде понятно объяснил .

Это сообщение отредактировал(а) Perchilla - 5.10.2004, 22:06

Цитата(Perchilla @ 5.10.2004, 19:05)

Есть метод проще, он работает с ограниченным количеством клеток (максимум 64x64 где то так ). Просто всегда выбираешь следующий ход, от которого есть наименьшее количество вариантов последующих ходов. Вроде понятно объяснил .

Не всегда, просто сначала пытаешься пойти в такую клетку.
Эта задача решается только полным перебором. Волновой алгоритм здесь не прокатит. Расставили мы единицы, а дальше? Надо хранить все варианты где-то. Все придет к тому же перебору, но еще париться с хранением...
Проще рекурсия. Пусть доска 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.
}

Вот примерно так, думаю, идея понятна

Для проверки можете использовать следующий факт: стандартную шахматную доску можно полностью обойти конем, не заходя в клетку дважды. И такой способ не один.

Существует строгое доказательство того, что прямоугольную доску M*N (M>3, N>3) можно всю обойти конем, побывав в каждой клетке по разу.

А так:
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