Задача 49: Мышка и зернышки

GetGrains.cs

using System;
using System.Linq;
					
public class Program
{
	public static int[] GetGrains(int[][] arr)
	{
		int m = arr.Length;
		int n = arr[0].Length;
		int[] maxGrainsWay = new int[n + m - 1];
		int i, j;
		
		// вспомогательный массив для хранения суммы зернышек по каждому маршруту
		int[,] grains = new int[m + 1, n + 1];
		for (i = 0; i <= m; i++)
		{
			for (j = 0; j <= n; j++)
			{
				grains[i, j] = i == 0 || j == 0 ? -1 : arr[i - 1][j - 1];
			}
		}
		
		grains[0, 1] = 0;
		for (i = 1; i <= m; i++)
		{
			for (j = 1; j <= n; j++)
			{
				var tmp = grains[i - 1, j];
				var tmp1 = grains[i, j - 1];
				grains[i, j] = Math.Max(grains[i - 1, j], grains[i, j - 1]) + grains[i, j];
			}
		}
		
		i = m; j = n; 
		int index = 1;
		maxGrainsWay[0] = arr[i - 1][j - 1];            
		while (i + j > 2)
		{
			if (grains[i - 1, j] > grains[i, j - 1])
			{
				maxGrainsWay[index] = arr[i - 2][j - 1];
				i--;
			}
			else
			{
				maxGrainsWay[index] = arr[i - 1][j - 2];
				j--;
			}
			index++;
		}
		
		return maxGrainsWay.Reverse().ToArray();
	}	
	
	public static void Main()
	{
		Console.WriteLine("UniLecs");
		int[][] arr = new int[][] 
		{
			new int[] { 3, 2, 4 },                
				new int[] { 3, 2, 4 },
				new int[] { 1, 5, 1 },
				
		};
		GetGrains(arr).ToList().ForEach(x => Console.Write("{0} ", x));
	}
}