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

namespace TravMerchant
{
    public class SolutionNode
    {
        public ReducableMatrix Matrix;
        public int? Value;
        public SolutionNode Parent;
        public SolutionNode Left;
        public SolutionNode Right;

        public SolutionNode(ReducableMatrix matrix)
        {
            Matrix = matrix;
            Parent = null;
            Value = matrix.CalculateLowerBound(0);
        }

        private SolutionNode(ReducableMatrix matrix, SolutionNode parent, int? lastSum, bool recalculate)
        {
            Matrix = matrix;
            Parent = parent;
            if (recalculate)
            {
                Value = matrix.CalculateLowerBound(lastSum);
            }
            else
            {
                matrix.CalculateLowerBound(lastSum);
                Value = lastSum;
            }
        }

        public bool HasChildren() => Left != null;

        public List<(int, int)> Solve()
        {
            var leaf = MinimalLeaf();
            for (; !leaf.IsSolved(); leaf = MinimalLeaf())
            {
                leaf.Calculate();
            }
            return leaf.Matrix.GetPath();
        }

        private SolutionNode MinimalLeaf()
        {
            if (HasChildren())
            {
                var leftMin = Left.MinimalLeaf();
                var rightMin = Right.MinimalLeaf();
                return leftMin.Value > rightMin.Value ? rightMin : leftMin;
            }
            return this;
        }

        public void Calculate()
        {
            int?[,] weights = Matrix.CalculateWeights();
            var point = Matrix.FindMaxWeightPoint(weights);

            var reducedMatrix = Matrix.Reduce(point.Item1, point.Item2);

            var unincludeMatrix = new ReducableMatrix(Matrix);
            unincludeMatrix[point.Item1, point.Item2] = null;

            Left = new SolutionNode(reducedMatrix, this, Value, true);
            Right = new SolutionNode(unincludeMatrix, this, Value + weights[point.Item1, point.Item2], false); //3 -- штраф за вес
        }

        public bool IsSolved()
        {
            return Matrix.GetLength(0) == 0;
        }

        public override string ToString()
        {
            return new StringBuilder().Append($"({(Value == null ? "∞" : Value.ToString())})").AppendLine().Append(Matrix.ToString()).ToString();
        }
    }
}