Программа которая возвращает минимальное количество прыжков - C#
Формулировка задачи:
Круг разбитый на 160 сегментов
Всего 16 секторов и 10 колец.
В дальнейшем каждый сегмент задается номером кольца (от 1 до 10 считая от центра) и номером сектора (от 1 до 16 по ходу часовой стрелки)
Например (1, 16) это сегмент, который расположен на первом кольце от центра и в 16 секторе.
На круге находится лягушка возвращена по ходу часовой стрелки.
Лягушка может прыгнуть в 5 точек относительно своего первоначального положения:
● на том же кольце на 3 сектора вперед
● на 1 кольцо ближе к центру и на 2 сектора вперед
● на 1 кольцо дальше от центра и на 2 сектора вперед
● на 2 кольца ближе к центру и на 1 сектор вперед
● на 2 кольца дальше от центра и на 1 сектор вперед
Лягушка не может выпрыгнуть за круг, не может развернуться, и не может прыгать через
центр.
Лягушка не может прыгать на сегменты, которые заняты деревьями (на рисунке (9, 14) и (8, 5))
Задание:
Напишите программу, которая возвращает минимальное количество прыжков, что необходимо сделать
лягушке для того, чтобы добраться из начального сегмента в конечном.
Входные параметры: начальный и конечный сегменты, количество деревьев, координаты
сегментов занятых деревьями.
В выводе программы необходимо отметить минимальное количество и минимальный путь, или
сообщение о невозможностью добраться из исходного положения в конечное.
Решение задачи: «Программа которая возвращает минимальное количество прыжков»
textual
Листинг программы
static class Program
{
/// <summary>
/// Прыжок
/// </summary>
/// <param name="сircle"></param>
/// <param name="x">Номер сектора откуда прыгаем</param>
/// <param name="y">Номер кольца откуда прыгаем</param>
/// <param name="dx">На сколько секторов прыгаем</param>
/// <param name="dy">На сколько колец прыгаем</param>
static void rec(int[,] circle, int x, int y, int dx=0, int dy=0)
{
// Сколько уже прыжков совершили
int n = circle[x, y];
// Новые координаты:
x = (x + dx) % 16; y += dy;
// завершаем рекурсию:
if (y < 0 || y >= 10 // Если прыгнули за круг или центр
|| circle[x, y] == -1 // Если в новых координатах стоит дерево
|| circle[x, y] > 0 && circle[x, y] < n) // Если уже был найден более коротнкий путь
return;
// Говорим, что в новые координаты можно добрать за n+1 прыжков
circle[x, y] = n + 1;
// Запускаем рекурсию по всем возможным направлениям:
rec(circle, x, y, 3, 0);
rec(circle, x, y, 1, -2);
rec(circle, x, y, 1, 2);
rec(circle, x, y, 2, 1);
rec(circle, x, y, 2, -1);
}
static void Main()
{
// Круг (заполнен нулями)
int[,] circle = new int[16, 10];
// Устанавливаем деревья:
circle[5-1, 8-1] = -1;
circle[14-1, 9-1] = -1;
// Начнем с точки 11,7
rec(circle, 11 - 1, 7 - 1);
// Теперь для каждого сегмента круга мы
// знаем сколько прыжков нужно, чтобы туда добраться
// Например,
Console.WriteLine("в сегмент (3,3) мы доберемся за:" + (circle[3 - 1, 3 - 1] - 1) + " прыжков");
// В общем случае:
Console.Write(" ");
for (int x = 0; x < 16; x++)
Console.Write("[{0,2}] ", x+1);
Console.WriteLine();
for (int y = 0; y < 10; y++)
{
Console.Write("[{0,2}] ", y+1);
for (int x = 0; x < 16; x++)
Console.Write("{0,4} ", circle[x, y] - 1);
Console.WriteLine();
}
Console.ReadLine();
}
}