Имеется шахматная доска 8х8. Предположим в каждой клетке доски содержится некоторое количество яблок. Шахматная фигура “конь” может ходить по классическим правилами хода коня. Оказываясь в очередной клетке, конь собирает все яблоки, которые в ней находятся. Имеется ограничения на количество ходов. Ваша программа должна принимать на вход следующие аргументы: максимальное число ходов, имя файла, содержащего схему заполнения шахматной доски яблоками. Строки в файле соответствуют строкам шахматной доски, строки разделяются переносами. Числа в строках разделяются пробелами. Ваша программа должна вывести максимально возможное количество собираемых яблок конем, при заданном ограничении ходов и произвольном выборе начальной позиции. Собственно, хотелось бы понять, каким образом/методом следует решать эту задачу. Сам код мне, конечно, нужен, но думаю и сам смогу написать программу, если пойму её основную идею. Была идея решать через жадный алгоритм, передвигаясь в клетку, содержащую в себе максимально возможное число яблок (сравнивал количество яблок в каждой из клеток, доступных в данный момент и шел в клетку с максимальным числом), но, как мне кажется, это решение, мягко говоря, не совсем верное. Задача должна содержать в себе рекурсию. Подайте идею решения данной проги или посоветуйте литературы по этой теме, пожалуйста. Заранее благодарю! :D
Ответ
Думаю, что подобные задачи решаются полным перебором. То есть, для каждой клетки делаем полный перебор ходов. Да, это будет долго, но... Специалисты могут решат задачу другим способом. Шахматная доска для коня - это граф. Кол-во яблок в клетке - это значение в вершине. Задача сводиться к поиску цепочки с максимальной суммой. В теории графов есть много алгоритмов для поиска кратчайшего пути, но думаю, они легко "перевернутся".
Комментариев нет:
Отправить комментарий