RobotAndChetnost

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

namespace RobotAndChetnost
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using (var sr = new StreamReader("input.txt"))
            {
                int n = int.Parse(sr.ReadLine());
                int[,] matrix = new int[n, n];
                for (int i = 0; i < n; i++)
                {
                    string[] newString = sr.ReadLine().Split(' ');
                    for (int j = 0; j < n; j++)
                    {
                        matrix[i, j] = int.Parse(newString[j]);
                    }
                }
                Console.WriteLine("Minimal");
                Console.WriteLine("ResultMin = " + MinWay(matrix));
                Console.WriteLine();
                Console.WriteLine("Maximum");
                Console.WriteLine("ResultMax = " + MaxWay(matrix));
                Console.ReadKey();
            }
        }
        //Если в клетке четное - вниз или направо
        //Если в кретке нечетное - направо
        public static int[,] DuplicateMatrix(int[,] matrix)
        {
            int[,] newmatrix = new int[matrix.GetLength(0), matrix.GetLength(0)];
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                for (int j = 0; j < matrix.GetLength(0); j++)
                {
                    newmatrix[i, j] = matrix[i, j];
                }
            }
            return newmatrix;
        }
        public static void FirstString(int[,] array)
        {
            for (int i = 1; i < array.GetLength(0); i++)//Заполняем первую строку
            {
                array[0, i] += array[0, i - 1];
            }
        }
        public static void AllColumn(int[,] array)
        {
            bool nechet = false;//Флаг встречаемости нечетного числа
            if (array[0, 0] % 2 != 0)//Проверяем самый первый элемент
            {
                nechet = true;
            }
            for (int i = 1; i < array.GetLength(0); i++)//Идём по всем остальным
            {
                if (!nechet)//Если нечетное не встретилось
                {
                    array[i, 0] += array[i - 1, 0];
                }
                else array[i, 0] = -1;//Иначе все последующие заменяем на -1, потому что мы до них не сможем дойти
                if (array[i, 0] % 2 != 0)//Проверяем текущий на нечетность
                {
                    nechet = true;
                }

            }

        }
        public static int MinWay(int[,] matrix)
        {
            int[,] array = DuplicateMatrix(matrix);

            FirstString(array);
            AllColumn(array);

            for (int i = 1; i < array.GetLength(0); i++)
            {
                for (int j = 1; j < array.GetLength(0); j++)
                {
                    int minEl = int.MaxValue;
                    if (matrix[i - 1, j] % 2 == 0 && array[i - 1, j] < minEl)//Если верхний четный (значит мы могли прийти сверху и верхний меньше минимального
                    {
                        minEl = array[i - 1, j];
                    }
                    if (array[i, j - 1] != -1 && array[i, j - 1] < minEl)//Если левый не -1 (значит мы могли прийти слева) и левый меньше минимального
                    {
                        minEl = array[i, j - 1];
                    }
                    if (minEl != int.MaxValue)
                    {
                        array[i, j] += minEl;
                    }
                    else array[i, j] = -1;
                }
            }
            PrintWay(matrix, array);
            return array[array.GetLength(0) - 1, array.GetLength(1) - 1];
        }
        public static int MaxWay(int[,] matrix)
        {
            int[,] array = DuplicateMatrix(matrix);

            FirstString(array);
            AllColumn(array);

            for (int i = 1; i < array.GetLength(0); i++)
            {
                for (int j = 1; j < array.GetLength(0); j++)
                {
                    int minEl = 0;
                    if (matrix[i - 1, j] % 2 == 0 && array[i - 1, j] > minEl)//Если верхний четный (значит мы могли прийти сверху и верхний меньше минимального
                    {
                        minEl = array[i - 1, j];
                    }
                    if (array[i, j - 1] != -1 && array[i, j - 1] > minEl)//Если левый не -1 (значит мы могли прийти слева) и левый меньше минимального
                    {
                        minEl = array[i, j - 1];
                    }
                    if (minEl != 0)//если минимальный существует
                    {
                        array[i, j] += minEl;
                    }
                    else array[i, j] = -1;//если никакой не подошёл
                }
            }
            PrintWay(matrix, array);
            return array[array.GetLength(0) - 1, array.GetLength(1) - 1];
        }
        public static void PrintWay(int[,] matrix, int[,] array)
        {
            Stack<int> stack = new Stack<int>(); //Последний зашёл - последний вышел
            for (int i = matrix.GetLength(0) - 1; i >= 0;)
            {
                for (int j = matrix.GetLength(0) - 1; j >= 0;)
                {
                    if (j > 0 && array[i, j] - array[i, j - 1] == matrix[i, j])//мы пришли слева
                    {
                        stack.Push(matrix[i, j]);
                        j--;
                    }
                    else if (i > 0 && array[i, j] - array[i - 1, j] == matrix[i, j])//мы пришли сверху
                    {
                        stack.Push(matrix[i, j]);
                        i--;
                    }
                    if(i == 0 && j == 0)
                    {
                        stack.Push(matrix[i, j]);
                        i--;
                        j--;
                    }
                }
            }
            Console.WriteLine("Way");
            for (int i = 0; i < stack.Count; i++)
            {
                Console.WriteLine(stack.Pop());//Pop - возвращает вершину и удаляет
            }
            Console.WriteLine();
        }
    }
}