.NET 4.x Динамическое программирование: задача о черепашке - C#
Формулировка задачи:
Задача о черепашке.
Дан 2х мерный массив с очками (длиной пути ну и.т.д.).
Найти кротчайший путь из точки
Но при таком
она работает не верно
вместо:
Она
А
в точкуБ
. Пример верной работы:
{ 1, 3, 4, 8 },
{ 5, 6, 2, 0 },
{ 1, 3, 4, 2 },
{ 0, 1, 8, 6 },
{ 7, 4, 5, 1 }
1 4 8
8 5 610 10
1 3 412
0 1 818
7 4 519
{ 1, 3, 4, 8 },
{ 5, 6, 2, 0 },
{ 1, 3, 4, 2 },
{ 0, 1, 8, 60 },
{ 7, 4, 5, 1 }
1 4 8
8 5 610 10
1 316
12
0 124
60 7 429
30
1 4 8
8 5 610 10
1 3 1612
0 1 2472
7 4 573
class Program
{
static public void print(int[,] a)
{
for (int i = 0; i < a.GetLength(0); i++, Console.WriteLine())
for (int j = 0; j < a.GetLength(1); j++)
Console.Write(a[i, j] + " ");
}
static void herepahka(int[,] a, int i, int j)
{
Console.WriteLine();
if (i + 1 < a.GetLength(0) && j + 1 < a.GetLength(1))
{
if (a[i, j] + a[i + 1, j] <= a[i, j] + a[i, j + 1])
{
a[i + 1, j] += a[i, j];
print(a);
herepahka(a, i + 1, j);
}
else
{
a[i, j + 1] += a[i, j];
print(a);
herepahka(a, i, j + 1);
}
}
else
{
if (i + 1 < a.GetLength(0))
{
a[i + 1, j] += a[i, j];
print(a);
herepahka(a, i + 1, j);
}
if (j + 1 < a.GetLength(1))
{
a[i, j + 1] += a[i, j];
print(a);
herepahka(a, i, j + 1);
}
print(a);
}
}
static void Main(string[] args)
{
Console.WriteLine("Vvedite razmer polia");
int[,] a = {
{ 1, 3, 4, 8 },
{ 5, 6, 2, 0 },
{ 1, 3, 4, 2 },
{ 0, 1, 8, 60 },
{ 7, 4, 5, 1 } };
print(a);
Console.WriteLine();
herepahka(a, 0, 0);
Console.ReadKey();
}
}
ap...
Решение задачи: «.NET 4.x Динамическое программирование: задача о черепашке»
textual
Листинг программы
int[,] a = {{ 0, 0, 0, 8 },
{ 5, 6, 0, 5 },
{ 0, 0, 0, 2 },
{ 0, 1, 8, 1 },
{ 0, 0, 0, 0 } };