Задание.
Дано прямоугольное поле D размером (N, M) клеток (двумерный массив). В каждой клетке написано число – вес клетки. Из клетки (a, b) можно попасть в клетки (a + 1, b), (a, b + 1) или (a + 1, b + 1). Вам надо попасть из клетки (0, 0) в клетку (N – 1, M – 1). Вес маршрута вычисляется как сумма весов посещенных клеток. Найдите вес минимального маршрута из (0, 0) в (N – 1, M – 1). Короче, вот формула:
G(0, 0) = D[0, 0]
G(i, 0) = G(i - 1, 0) + D[i, 0], i > 0
G(0, j) = G(0, j - 1) + D[0, j], j > 0
G(i, j) = min(G(i - 1, j - 1), G(i - 1, j), G(i, j - 1)) + D[i, j], i > 0, j > 0
F(D) = G(N - 1, M - 1)
Никак не получается написать правильно работающую рекурсивную функцию которая это все вычисляет. Вот мой вариант, но считает неверно. В чем ошибка? Как будет правильно?
public static int sum =0;
static int G(int i, int j, int[,] D)
{
if (i == 0 && j == 0)
return D[0, 0];
if (j==0&&i!=0)
{ sum = G(i - 1, 0,D) + D[i, 0];
return G(i - 1, 0, D);
}
if (i==0&&j!=0)
{
sum = G(0, j - 1, D) + D[0, j];
return G(0, j - 1, D);
}
if (i!=0&j!=0)
{
sum = Math.Min(Math.Min(G(i - 1, j - 1, D), G(i - 1, j, D)), G(i, j - 1, D)) + D[i, j];
return G(i - 1, j - 1, D);
}
return 1;
}
Переписал функцию без суммы, все ровно считает неправильно.
static int G(int i, int j, int[,] D)
{
if (i == 0 && j == 0)
{
return D[0, 0];
}
if (j==0&&i!=0)
{
return G(i - 1, 0, D) + D[i, 0];
}
if (i==0&&j!=0)
{
return G(0, j - 1, D) + D[0, j];
}
if (i!=0&j!=0)
{
return Math.Min(Math.Min(G(i - 1, j - 1, D), G(i - 1, j, D)), G(i, j - 1, D)) + D[i, j];
}
return 1;
}