Найти сумму максимальных значений

[WonderDoggy]

Доброго времени суток. Вот условие задачи: Выставка проходит в зале, разделенном на 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, max = 0;
            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("Вот он, выставочный зал: ");
            Random r = new Random();
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < m; j++)
                {
                    mas[i, j] = r.Next(9);
                    Console.Write(mas[i, j] + "\t");
                }
                Console.WriteLine();
            }

            Console.WriteLine();
            //for (i = 0; i < n; i++)
            //{
            //    for (j = 0; j < m; j++)
            //    {
            //        dubl[i, j] = 0;
            //        Console.Write(dubl[i, j] + "\t");
            //    }
            //    Console.WriteLine();
            //}
            Console.WriteLine("------------------------------------------------");
            Console.WriteLine("Введите количество минут на посещение выставки: ");
            k = Int32.Parse(Console.ReadLine());
            int p;
            int e = 0;
            int g = 0;
            int h = 0;
            int s = 0;
            p = mas[0, 0];

            for (i = 0; i < 1; i++)
            {
                for (j = 0; j < k; j++)
                {
                    if (mas[i, j + 1] > mas[i + 1, j])
                    {
                        //mas[i, j] = mas[i, j] + mas[i, j + 1];
                        p += mas[i, j + 1];
                    }
                    if (mas[i + 1, j] > mas[i, j + 1])
                    {
                        // mas[i, j] = mas[i + 1, j] + mas[i, j];
                        e += mas[i + 1, j];
                    }
                    if ((i >= 1 && j >= 1) || (i >= 1 || j >= 1))
                    {
                        if (mas[i - 1, j] > mas[i, j + 1] && mas[i - 1, j] > mas[i + 1, j] && mas[i - 1, j] > mas[i, j - 1])
                        {
                            g += mas[i - 1, j];
                        }
                        if (mas[i, j - 1] > mas[i, j + 1] && mas[i, j - 1] > mas[i + 1, j] && mas[i, j - 1] > mas[i - 1, j])
                        {
                            h += mas[i, j - 1];
                        }
                    }
                    int[] dubl = new int[] { p, e, g, h };
                    Console.WriteLine();

                    for (i = 0; i < 3; i++)
                        Console.Write(dubl[i] + " ");

                    for (i = 0; i < 3; i++)
                    {
                        if (max < dubl[i])
                            dubl[i] = max;
                    }
                    s = max + s;
                    Console.Write(p + "\t");
                }
            }

            //for (i = 0; i < 1; i++)
            //{
            //    for (j = 0; j < k; j++)
            //    {
                    
            //        if (mas[i, j + 1] > mas[i + 1, j])
            //        { 
            //            //mas[i, j] = mas[i, j] + mas[i, j + 1];
            //            p+= mas[i, j+1];
            //        } 
            //        if (mas[i + 1, j] > mas[i, j + 1])
            //        {
            //           // mas[i, j] = mas[i + 1, j] + mas[i, j];
            //            p+= mas[i+1, j];
            //        }
                    
            //       if (i>=1 && mas[i - 1, j] > mas[i, j + 1] && mas[i - 1, j] > mas[i + 1, j] && mas[i - 1, j] > mas[i, j - 1])
            //            {
            //                p+= mas[i - 1, j];
            //            }
            //       if (j >= 1 && mas[i, j-1] > mas[i, j + 1] && mas[i, j-1] > mas[i + 1, j] && mas[i, j-1] > mas[i-1, j])
            //       {
            //           p += mas[i, j-1];
            //       }
            //        Console.Write(p+ "\t");
            //        //cur = Max(mas[i + 1, j], mas[i - 1, j], mas[i, j + 1], mas[i, j - 1]) + mas[i, j];
            //    }
            //}
            
            Console.WriteLine("Максимальная сумма составляет: " + s);
            //for (i = 0; i < n; i++)
            //{
            //    for (j = 0; j < m; j++)
            //    {
            //        Console.Write(mas[i, j] + "\t");
            //    }
            //    Console.WriteLine();
            //}
            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]

а зачем новая тема, чем Вас предыдущая ваш тема не устроила?

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

[Аватар]

полагаю min(k,m*n)

[Serge_Bliznykov]

Сообщение от Аватар

полагаю min(k,m*n)

Т.е. Вы думаете, что стоимость каждого предмета (одного) в каждом павильоне одинакова?!!

Но ведь об этом в условии задачи не сказано однозначно!
И задача вырождается в какую-то банальщину!


p.s. хотя, конечно, в условии и не сказано, что каждый предмет имеет свою стоимость!

p.p.s. поиском нашёл НОРМАЛЬНЫЕ условия этой задачи:
607. E - Малый бизнес
или тут - http://www.snarknews.info/files/snws/probs/snws3.pdf

Выставка компьютерных фирм проходит в зале, разделенном на N ´ N павильонов. Каждая из четырех стен любого павильона, кроме граничных стен, имеет дверь в соседний павильон. Каждый павильон занят какой-либо фирмой, которая раздает посетителям предметы какого-либо одного вида (ручки, пакеты, проспекты и т.д.). Начинающий компьютерный бизнесмен Вася желает набрать бесплатных предметов на возможно большую сумму. К сожалению, в одни руки выдают только по одному предмету за одно посещение, поэтому Вася вынужден постоянно переходить из павильона в павильон. Посещать один и тот же павильон можно сколько угодно раз. На получение одного предмета Васе требуется одна минута. Требуется определить максимальную сумму, на которую Вася может набрать предметов в течение K минут. Зал определяется квадратной матрицей, содержащей стоимость предметов, выдаваемых в каждом павильоне. , 2 £ N £ 100, 0 < aij <10 000,
aij ÎZ
Путь Васи всегда начинается с павильона (1,1) и состоит из последовательности пар координат (i1, j1), (i2, j2),… ,(iK, jK), 1 £ K £ 10 000, в которой для любого t 1 £ t < K 1 £ it, jt £ N и . По данным N, K и матрице A найти (it, jt), t=1..K такие, что i1 = j1 = 1 и сумма максимальна.
Входные и выходные данные
Первая строка входного файла содержит числа N и K. Следующие N строк представляют 1,2,…,N-ю строки матрицы, по N чисел в строке.
Выходной файл должен содержать единственное число — максимальную сумму.

[Аватар]

Там о стоимости предметов в павильонах вообще ни слова не сказано. Значит равна )) Иначе задача лишена смысла до тех пор, пока не будет задаваться стоимость в каждом павильоне. Тогда все гораздо интересней ))

[Serge_Bliznykov]

Сообщение от Аватар

Там о стоимости предметов в павильонах вообще ни слова не сказано. Значит равна )) Иначе задача лишена смысла до тех пор, пока не будет задаваться стоимость в каждом павильоне. Тогда все гораздо интересней ))

то, что автору темы дали кривое описание задачи (или он сам её так криво скопировал), совсем не означает, что задача такая уж банально-простая
Конечно, в каждой клетке своя стоимость предмета. и сколько раз посетил клетку - столько раз получил эту стоимость.
Иначе, разумеется, тут и решать нечего.

вот описание входных данных и пример ввода/вывода:

Формат входного файла:
В первой строке записаны числа N и K, 2 <= N <= 100, 1 <= K <= 10000.
В следующих N строках записаны целые значения элементов 1, 2, …, N-ой строки матрицы Ai1, Ai2, …, AiN, по N чисел в строке, 0 < Aij < 10000.

Формат выходного файла:
В первой строке вывести полученный результат – максимальную сумму.

Пример ввода:

5 7 
1 1 1 1 1 
1 1 3 1 9 
1 1 6 1 1 
1 1 3 1 1 
1 1 1 1 1

Пример вывода:
21

вот, нашёл решение через динамику. На Pascal.
взято тут - http://forum.ru-board.com/topic.cgi?...&limit=1&m=1#1

(с) creer

var 
  n, k: integer; 
  a, c, p: array [0..101, 0..101] of integer; 
  i, j, kk: integer; 
 
function max(v1, v2, v3, v4: integer):integer; 
begin 
  if (v1>=v2) and (v1>=v3) and (v1>=v4) then 
    max:=v1; 
  if (v2>=v1) and (v2>=v3) and (v2>=v4) then 
    max:=v2; 
  if (v3>=v1) and (v3>=v2) and (v3>=v4) then 
    max:=v3; 
  if (v4>=v1) and (v4>=v2) and (v4>=v3) then 
    max:=v4; 
end; 
 
begin 
  readln(n, k); 
  for i:=1 to n do 
  begin 
    for j:=1 to n do 
      read(a[i,j]); 
    readln; 
  end; 
 
  for kk:=1 to k do 
  begin 
  p:=c; 
    for i:=1 to n do 
      for j:=1 to n do 
        c[i,j]:=max(p[i-1][j], p[i+1][j], p[i][j-1], p[i][j+1])+a[i][j]; 
  end; 
  writeln(c[1,1]); 
end.

разумеется, чтобы выдать не только максимальное значение, а и путь,
решение надо чуток допилить!

[WonderDoggy]

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

что автору темы дали кривое описание задачи

К сожалению, мне именно таким условие и выдали. Нам специально поменяли немного условия в задачах чтобы не было легкой возможности найти в инете решение. А по поводу стоимости: каждая клетка (или же элемент массива) и является стоимостью предмета, и при возвращении в ту или иную клетку сумма повторно не должна считаться.

[Serge_Bliznykov]

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

К сожалению, мне именно таким условие и выдали.Нам специально поменяли немного условия в задачах

вот, я так и понял, что специально не очень умные люди испортили нормальную задачу своими кривыми формулировками.

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

А по поводу стоимости: каждая клетка (или же элемент массива) и является стоимостью предмета

ткните пальцев, где об этом сказано в условиях задачи!
Если об этом не сказано в условиях задачи, откуда Вы это взяли?
Интуиция? Голос свыше? Тайное послание от Юстаса?
Или просто придумали?

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

и при возвращении в ту или иную клетку сумма повторно не должна считаться

а это откуда взялось?!
раз посещать можно многократно? да ещё и про одни руки зачем-то сказано!

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

Каждый павильон раздает посетителям предмет одного вида, выдают только один раз в одни руки. Однако посещать данный павильон можно сколь угодно раз.

подразумевается один раз в одни руки при каждом посещении этого павильона? Если это не так, почему в условии об этом не сказано?

А где ограничения на входные данные?
Размеры N и M чем-то ограничены? Матрицу 1000000 на 4000000000 решите?
А стоимость каждого предмета? Если стоимость предмета от 1 до 4000000000 есть решение задачи?

вот поэтому я и говорю, не очень квалифицированные у Вас учителя, которые Вас криво учат.
Разумеется, всё сказанное - это исключительно моё личное мнение, IMHO.
Это Вам учиться, Вам решать эту не очень прямую задачу и Вам её сдавать.



p.s. чувствую, что в задаче про расставленных мышах тот же изобретатель классическую задачу испоганил так, чтобы решение в интернете нельзя было найти. Ну а то, что задача при этом стала бессмысленное, это уже не так важно, это, так сказать, побочный эффект!

[WonderDoggy]

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

ткните пальцев, где об этом сказано в условиях задачи!

Это мой фейл, прошу прощения. Это я выяснил после уточнения условия у преподавателя. Я говорю и про стоимости, и про то, что сумма с павильоном не считается по возвращении в предыдущий. Собственно поэтому я ее и скинул сюда в надежде на какое-нибудь объяснение или помощь

[WonderDoggy]

В общем решил я задачу, не совсем сам конечно, мне помогли, однако все же она решена. Вот скидываю сюда, вдруг кому пригодится:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Threading;
using System.Data;

namespace ConsoleApplication1
{
    class Program
    {
        static Random rnd = new Random();
        static void Main(string[] args)
        {
            Console.Write("Введите n=");
            int n = int.Parse(Console.ReadLine());
            Console.Write("Введите m=");
            int m = int.Parse(Console.ReadLine());
            int[,] labirinth = new int[n, m];
            for (int i = 0; i < labirinth.GetLength(0); i++)
            {
                for (int j = 0; j < labirinth.GetLength(1); j++)
                {
                    labirinth[i, j] = rnd.Next(1, 10);
                    Console.Write(labirinth[i, j] + "  ");
                }
                Console.WriteLine();
            }
            Console.Write("Количество минут на посещение выставки=");
            int k = int.Parse(Console.ReadLine());
            k = k + 1;
            Console.WriteLine("Максимальная сумма предметов составляет:");
            Console.WriteLine(MaxSum(labirinth, k));
            Console.ReadKey(true);
        }
        static int MaxSum(int[,] array, int t, int x = 0, int y = 0, int sum = 0)
        {
            array = (int[,])array.Clone();
            sum += array[x, y];
            array[x, y] = 0;
            if (--t == 0) return sum;
            if (x == 0)
            {
                if (y == 0) return Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum));
                if (y == array.GetLength(1) - 1) return Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y - 1, sum));
                return Math.Max(Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum)), MaxSum(array, t, x, y - 1, sum));
            }
            if (x == array.GetLength(0) - 1)
            {
                if (y == 0) return Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y + 1, sum));
                if (y == array.GetLength(1) - 1) return Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y - 1, sum));
                return Math.Max(Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y + 1, sum)), MaxSum(array, t, x, y - 1, sum));
            }
            if (y == 0)
            {
                return Math.Max(Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum)), MaxSum(array, t, x - 1, y, sum));
            }
            if (y == array.GetLength(1) - 1)
            {
                return Math.Max(Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x + 1, y, sum)), MaxSum(array, t, x, y - 1, sum));
            }
            return Math.Max(Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum)), Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y - 1, sum)));
        }
    }
}

Задача решалась методом рекурсивного обхода.