Посчитать сумму ближайших максимальных элементов матрицы

[WonderDog]

Всем доброго времени суток. Вот условие задачи: Выставка проходит в зале, разделенном на MxN павильонов. Каждая из 4 стен имеет дверь в соседний павильон (кроме граничных). Каждый павильон раздает посетителям предмет одного вида, выдают только один раз в одни руки. Однако посещать данный павильон можно сколь угодно раз. Путь начинается с (1,1) и состоит и последовательности координат. Необходимо выяснить, на какую максимальную сумму можно набрать предметов в течение К минут, если на посещение одного павильона дается 1 минута.
Вот что мне удалось сделать:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m, i, j, k;
            Console.WriteLine("Введите n: ");
            n = Int32.Parse(Console.ReadLine());
            Console.WriteLine("Введите m: ");
            m = Int32.Parse(Console.ReadLine());
            if ((m == 0 || n == 0) || (m < 0 || n < 0) || (m == 0 && n == 0) || (m < 0 && n < 0))
            {
                Console.WriteLine("Ошибка, не корректно введено значение!");
            }
            int[,] mas = new int[n, m];
            Console.WriteLine();
            Console.WriteLine("Введите элементы массива: ");
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < m; j++)
                {
                    mas[i, j] = int.Parse(Console.ReadLine());
                }
            }
            Console.WriteLine("Вот он, выставочный зал: ");
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < m; j++)
                {
                    Console.Write(mas[i, j] + "\t");
                }
                Console.WriteLine();
            }
            Console.WriteLine("------------------------------------------------");
            Console.WriteLine("Введите количество минут на посещение выставки: ");
            k = Int32.Parse(Console.ReadLine());
            double cur = mas[0, 0];

            for (i = k; i > 0; i--)
            {
                for (j = k; j > 0; j--)
                {
                            cur = Max(mas[i + 1, j], mas[i - 1, j], mas[i, j + 1], mas[i, j - 1]) + mas[i, j];
                }
            }
            Console.WriteLine("Максимальная сумма составляет: " + cur);
            Console.ReadKey();
        }

        public static int Max(int v1, int v2, int v3, int v4)
        {
            return Math.Max(Math.Max(v1, v2), Math.Max(v3, v4));
        }
    }
}

В общем проблема в поиске этих ближайших максимальных и, соответственно, их суммировании их. Подскажите пожалуйста как сделать, заранее очень благодарен.

[Serge_Bliznykov]

задача ОЧЕНЬ похожа на те, которые принято решать через динамику (ДП).

а ещё можно попытаться через рекурсивный обход с возвратом искать максимум.
Но это только если ограничения есть на входные данные, иначе, для больших K не хватит времени и стека на обход всех вариантов.

павильонов по условию M x N , а у Вас N x M (мелочь, но неприятно)

[WonderDog]

Сообщение от Serge_Bliznykov

а ещё можно попытаться через рекурсивный обход с возвратом искать максимум.

Про это я тоже думал, и мне говорили что так даже проще наверное будет, но я немного не шарю, собственно поэтому до сих пор и не сделал.

Сообщение от Serge_Bliznykov

павильонов по условию M x N , а у Вас N x M (мелочь, но неприятно)

Там разницы нет на самом деле, просто я по привычке наоборот поставил.