using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TravMerchant
{
    public class ReducableMatrix
    {
        private int?[,] matrix;

        private SortedSet<int> rowReduces = new SortedSet<int>();
        private SortedSet<int> columnReduces = new SortedSet<int>();

        private List<(int, int)> path = new List<(int, int)>();

        public ReducableMatrix(int?[,] matrix)
        {
            //Конструктор, клонирующий матрицу, для того, чтобы не затрагивать исходную по ходу программы
            this.matrix = (int?[,])matrix.Clone();
        }

        // Клонирующий конструктор
        public ReducableMatrix(ReducableMatrix matrix)
        {
            this.matrix = (int?[,])matrix.matrix.Clone();
            foreach (int reduce in matrix.rowReduces)
                rowReduces.Add(reduce);
            foreach (int reduce in matrix.columnReduces)
                columnReduces.Add(reduce);
            path.AddRange(matrix.path);
        }

        private ReducableMatrix(ReducableMatrix matrix, int row, int column) : this(matrix)
        {
            this.matrix[column, row] = null;
            rowReduces.Add(row);
            columnReduces.Add(column);
            path.Add((row, column));
        }

        //Доступ по локал координатам 
        public int? this[int i, int j]
        {
            get
            {
                var coords = Unreduce(i, j);
                return matrix[coords.Item1, coords.Item2];
            }
            set
            {
                var coords = Unreduce(i, j);
                matrix[coords.Item1, coords.Item2] = value;
            }
        }

        public int GetLength(int dimension) => matrix.GetLength(dimension) - rowReduces.Count;

        //возврат копии матрицы без строки и ряда
        public ReducableMatrix Reduce(int row, int column)
        {
            var p = Unreduce(row, column);
            return new ReducableMatrix(this, p.Item1, p.Item2);
        }

        //перевод локал в глобал
        private (int, int) Unreduce(int row, int column)
        {
            foreach (var reduce in rowReduces)
            {
                if (row >= reduce)
                    row++;
            }
            foreach (var reduce in columnReduces)
            {
                if (column >= reduce)
                    column++;
            }
            return (row, column);
        }

        public int[] RowMinimums()
        {
            int[] minimums = new int[GetLength(0)];
            for (int i = 0; i < GetLength(0); i++)
            {
                minimums[i] = int.MaxValue;
                for (int j = 0; j < GetLength(1); j++)
                {
                    if (this[i, j] == null)
                        continue;
                    if (minimums[i] > this[i, j])
                        minimums[i] = (int)this[i, j];
                }
            }
            return minimums;
        }
        
        public int[] ColMinimums()
        {
            int[] minimums = new int[GetLength(1)];
            for (int j = 0; j < GetLength(1); j++)
            {
                minimums[j] = int.MaxValue;
                for (int i = 0; i < GetLength(0); i++)
                {
                    if (this[i, j] == null)
                        continue;
                    if (minimums[j] > this[i, j])
                        minimums[j] = (int)this[i, j];
                }
            }
            return minimums;
        }
        //Посчитать нижнюю границу + редукция строк и столбцов. 
        public int? CalculateLowerBound(int? lastSum)
        {
            int[] rowMinimums = RowMinimums();
            for (int i = 0; i < GetLength(0); i++)
            {
                for (int j = 0; j < GetLength(1); j++)
                {
                    if (this[i, j] != null)
                        this[i, j] -= rowMinimums[i];
                }
            }

            int[] colMinimums = ColMinimums();
            for (int i = 0; i < GetLength(0); i++)
            {
                for (int j = 0; j < GetLength(1); j++)
                {
                    if (this[i, j] != null)
                        this[i, j] -= colMinimums[j];
                }
            }

            return rowMinimums.Sum() + colMinimums.Sum() + lastSum;
        }

        public int?[,] CalculateWeights()
        {
            int?[,] weights = new int?[GetLength(0), GetLength(1)];
            for (int i = 0; i < GetLength(0); i++)
            {
                for (int j = 0; j < GetLength(1); j++)
                {
                    if (this[i, j] == 0)
                    {
                        int? min = null;
                        for (int k = 0; k < GetLength(0); k++)
                        {
                            if (this[i, j] == null || j == k)
                                continue;
                            if (min == null || this[i, k] < min)
                                min = this[i, k];
                        }
                        weights[i, j] = min;
                        min = null;
                        for (int k = 0; k < GetLength(1); k++)
                        {
                            if (this[i, j] == null || i == k)
                                continue;
                            if (min == null || this[k, j] < min)
                                min = this[k, j];
                        }
                        weights[i, j] += min;
                    }
                    else
                        weights[i, j] = 0;
                }
            }
            return weights;
        }

        public (int, int) FindMaxWeightPoint(int?[,] weights)
        {
            var point = (0, 0);
            int max = 0;
            for (int i = 0; i < weights.GetLength(0); i++)
            {
                for (int j = 0; j < weights.GetLength(1); j++)
                {
                    if (weights[i, j] == null)
                        return (i, j);
                    if (weights[i, j] > max)
                    {
                        max = (int)weights[i, j];
                        point = (i, j);
                    }
                }
            }
            return point;
        }

        public List<(int, int)> GetPath()
        {
            return new List<(int, int)>(path);
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < GetLength(0); i++)
            {
                for (int j = 0; j < GetLength(1); j++)
                {
                    if (this[i, j] == null)
                        sb.Append("M  ");
                    else
                        sb.Append(string.Format("{0,-3}", this[i, j]));
                }
                sb.AppendLine();
            }
            return sb.ToString();
        }
    }
}