RobotAndZero

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

namespace Robot
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[,] data;
            int N;
            using (var sr = new StreamReader("input.txt"))
            {
                N = int.Parse(sr.ReadLine()); //Читаем из файла размер матрицы
                data = new int[N, N];
                for (int i = 0; i < N; i++)
                {
                    string[] str = sr.ReadLine().Split(' '); //Читаем построчно элементы
                    for (int j = 0; j < N; j++)
                    {
                        data[i, j] = int.Parse(str[j]);//Заносим в матрицу
                    }
                }
                int MinValue = SearchMinPath(data, N);
                Console.WriteLine("MinValue = " + MinValue);
                int MaxValue = SearchMaxPath(data, N);
                Console.WriteLine("MaxValue = " + MaxValue);
                Console.ReadKey();
            }
        }
        public static int SearchMaxPath(int[,] array, int N)
        {
            int[,] newArray = new int[N, N];
            for (int i = 0; i < N; i++) //Копируем матрицу
            {
                for (int j = 0; j < N; j++)
                {
                    newArray[i, j] = array[i, j];
                }
            }
            bool flagIfZero = false;
            for (int i = 1; i < N; i++) //Первая строка
            {
                if (flagIfZero)
                {
                    newArray[i, 0] = 0;
                }
                else if (newArray[i, 0] != 0)
                {
                    newArray[i, 0] = newArray[i, 0] + newArray[i - 1, 0];
                }
                else flagIfZero = true;
            }

            flagIfZero = false;

            for (int i = 1; i < N; i++) //Первый столбец
            {
                if (flagIfZero)
                {
                    newArray[0, i] = 0;
                }
                else if (newArray[0, i] != 0)
                {
                    newArray[0, i] = newArray[0, i] + newArray[0, i - 1];
                }
                else flagIfZero = true;
            }

            for (int i = 1; i < N; i++) //Заполнение центра матрицы (без боковых контуров)
            {
                for (int j = 1; j < N; j++)
                {
                    int MaxElement = SearchMaxElement(newArray, i, j); //Ищем максимальный элемент вокруг текущего в матрице
                    if(MaxElement == 0)
                    {
                        newArray[i, j] = 0;
                    }
                    else newArray[i, j] = newArray[i, j] + MaxElement;//Прибавляем к текущему максимум
                }
            }
            int k = N - 1; int l = N - 1;
            int current = newArray[k, l];
            List<int> path = new List<int>();
            path.Add(array[k,l]);
            while(current != newArray[0,0])//Вывод пути
            {
                if (k > 0 && current - newArray[k - 1, l] == array[k, l])//Проверка с верхним
                {
                    path.Add(array[k - 1, l]);
                    current = newArray[k - 1, l];
                    k--;
                }
                else if (l > 0 && current - newArray[k, l - 1] == array[k, l])//Проверка с левым
                {
                    path.Add(array[k, l - 1]);
                    current = newArray[k, l - 1];
                    l--;
                }
            }
            Console.Write("Path for max: ");
            for (int i = path.Count-1; i >= 0; i--)
            {
                Console.Write(" " + path[i]);
            }
            Console.WriteLine();
            return newArray[N - 1, N - 1];
        }
        public static int SearchMaxElement(int[,] array, int i, int j)
        {
            int maxElement = -1;
            bool flagMaxElement = false;
            if (array[i - 1, j] > maxElement && array[i, j] != 0 && array[i - 1, j] != 0) //Проверяем с верхнимс левым
            {
                maxElement = array[i - 1, j];
                flagMaxElement = true;
            }
            if (array[i, j - 1] > maxElement && array[i, j] != 0 && array[i, j - 1] != 0) //Проверяем с левым
            {
                maxElement = array[i, j - 1];
                flagMaxElement = true;
            }
            if (flagMaxElement)
            {
                return maxElement;
            }
            else return 0;
        }
        public static int SearchMinPath(int[,] array, int N)
        {
            int[,] newArray = new int[N, N];
            for (int i = 0; i < N; i++) //Копируем матрицу
            {
                for (int j = 0; j < N; j++)
                {
                    newArray[i, j] = array[i, j];
                }
            }
            bool flagIfZero = false;
            for (int i = 1; i < N; i++) //Первая строка
            {
                if (flagIfZero)
                {
                    newArray[i, 0] = 0;
                }
                else if (newArray[i, 0] != 0)
                {
                    newArray[i, 0] = newArray[i, 0] + newArray[i - 1, 0];
                }
                else flagIfZero = true;
            }

            flagIfZero = false;

            for (int i = 1; i < N; i++) //Первый столбец
            {
                if (flagIfZero)
                {
                    newArray[0, i] = 0;
                }
                else if (newArray[0, i] != 0)
                {
                    newArray[0, i] = newArray[0, i] + newArray[0, i - 1];
                }
                else flagIfZero = true;
            }

            for (int i = 1; i < N; i++) //Заполнение центра матрицы (без боковых контуров)
            {
                for (int j = 1; j < N; j++)
                {
                    int MinElement = SearchMinElement(newArray, i, j); //Ищем минимальный элемент вокруг текущего в матрице
                    if(MinElement == 0)
                    {
                        newArray[i, j] = 0;
                    }
                    else newArray[i, j] = newArray[i, j] + MinElement;//Прибавляем к текущему минимум
                }
            }
            int k = N - 1; int l = N - 1;
            int current = newArray[k, l];
            List<int> path = new List<int>();
            path.Add(array[k, l]);
            while (current != newArray[0, 0])//Вывод пути
            {
                if (k > 0 && current - newArray[k - 1, l] == array[k, l])//Проверка с верхним
                {
                    path.Add(array[k - 1, l]);
                    current = newArray[k - 1, l];
                    k--;
                }
                else if (l > 0 && current - newArray[k, l - 1] == array[k, l])//Проверка с левым
                {
                    path.Add(array[k, l - 1]);
                    current = newArray[k, l - 1];
                    l--;
                }
            }
            Console.Write("Path for min: ");
            for (int i = path.Count - 1; i >= 0; i--)
            {
                Console.Write(" " + path[i]);
            }
            Console.WriteLine();
            return newArray[N - 1, N - 1];

        }
        public static int SearchMinElement(int[,] array, int i, int j)
        {
            int minElement = int.MaxValue;
            bool flagMinElement = false;
            if (array[i - 1, j] < minElement && array[i, j] != 0 && array[i - 1, j] != 0) //Проверяем с верхнимс левым
            {
                minElement = array[i - 1, j];
                flagMinElement = true;
            }
            if (array[i, j - 1] < minElement && array[i, j] != 0 && array[i, j - 1] != 0) //Проверяем с левым
            {
                minElement = array[i, j - 1];
                flagMinElement = true;
            }
            if (flagMinElement)
            {
                return minElement;
            }
            else return 0;
        }
    }
}