using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Reflection.Metadata;
using System.Text;
using System.Threading.Tasks;
using System.Xml.Linq;

namespace DO_Lab4
{
    public static class MyExtensions
    {
        public static void Fill<T>(this T[,] array, T value)
        {
            for (int i = 0; i < array.GetLength(0); i++)
            {
                for (int j = 0; j < array.GetLength(1); j++)
                {
                    array[i, j] = value;
                }
            }
        }
        public static void Remove(this ref Direction value, Direction flags)
        {
            value = value & ~flags;
        }
        public static void Add(this ref Direction value, Direction flags)
        {
            value |= flags;
        }
        public static bool Contains(this Direction value, Direction flag)
        {
            return (value & flag) != Direction.None;
        }

    }
    [Flags]
    public enum Direction
    {
        None = 0,
        Left = 1,
        Right = 2,
        Up = 4,
        Down = 8,
        All = 16
    }
    class Vertex
    {
        public int Row;
        public int Column;
        public Direction AcceptableDirections;
        public Vertex(int row, int column, Direction directions)
        {
            this.Row = row;
            this.Column = column;
            AcceptableDirections = directions;
        }
        public override bool Equals(object obj)
        {
            if (obj == null || GetType() != obj.GetType())
            {
                return false;
            }

            Vertex other = (Vertex)obj;
            return (Row == other.Row && Column == other.Column);
        }
    }
    struct Consumer
    {
        public int transportationCosts;
        public int metNeeds;
        public int sign;
    }

    internal class PotencialMethod
    {
        const int FICTITIOUS_FILLING = int.MaxValue - 1;
        int[] needs;
        int[] stocks;
        int[] u;
        int[] v;
        Consumer[,] consumers;

        //------------------------
        private void printArr()
        {
            for (int i = 0; i < consumers.GetLength(0) + 1; i++)
            {
                if (i < consumers.GetLength(0))
                {
                    for (int j = 0; j < consumers.GetLength(1) + 1; j++)
                    {
                        if (j < consumers.GetLength(1))
                        {
                            Console.Write($"{consumers[i, j].transportationCosts} / {consumers[i, j].metNeeds,-4} ");
                        }
                        else
                        {
                            Console.WriteLine(stocks[i]);
                        }
                    }
                }
                else
                {
                    for (int j = 0; j < needs.Length; j++)
                    {
                        Console.Write($"{needs[j],3} ");
                    }
                }
            }

            int sum = 0;
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    sum += consumers[i, j].transportationCosts * consumers[i, j].metNeeds;
                }
            }

            //Console.WriteLine("\nSUM  = " + sum);
        }

        private void printSigns()
        {
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    Console.Write($"{consumers[i, j].sign,-3} ");
                }
                Console.WriteLine();
            }
        }
        //------------------------
        public PotencialMethod(string path)
        {
            string[] data = File.ReadAllLines(path);
            stocks = new int[data.Length - 1];
            u = new int[stocks.Length];
            Array.Fill(u, int.MinValue);
            needs = new int[data.Last().Split(' ').Length];
            v = new int[needs.Length];
            Array.Fill(v, int.MinValue);

            consumers = new Consumer[stocks.Length, needs.Length];

            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    //consumers[i, j].metNeeds = 0;
                }
            }

            for (int i = 0; i < data.Length; i++)
            {
                string[] current = data[i].Split(' ');
                if (i < data.Length - 1)
                {
                    for (int j = 0; j < current.Length; j++)
                    {
                        if (j < current.Length - 1)
                        {
                            consumers[i, j].transportationCosts = int.Parse(current[j]);
                        }
                        else
                        {
                            stocks[i] = int.Parse(current[j]);
                        }
                    }
                }
                else
                {
                    for (int j = 0; j < current.Length; j++)
                    {
                        needs[j] = int.Parse(current[j]);
                    }
                }
            }

            // minimumElementMethod();
            //printArr();
        }

        private (int, int) findMin()
        {
            int min = int.MaxValue;
            int iVal = -1, jVal = -1;

            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                if (stocks[i] == 0) continue;

                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (needs[j] != 0 && consumers[i, j].transportationCosts < min)
                    {
                        min = consumers[i, j].transportationCosts;
                        iVal = i;
                        jVal = j;
                    }
                }
            }
            return (iVal, jVal);
        }
        private void minimumElementMethod()
        {
            bool isSolved = false;

            while (!isSolved)
            {
                (int iVal, int jVal) = findMin();

                int valueToTransport = Math.Min(stocks[iVal], needs[jVal]);
                consumers[iVal, jVal].metNeeds = valueToTransport;
                stocks[iVal] -= valueToTransport;
                needs[jVal] -= valueToTransport;

                isSolved = true;
                for (int i = 0; i < needs.Length; i++)
                {
                    if (needs[i] != 0)
                    {
                        isSolved = false;
                        break;
                    }
                }
            }
        }
        private void northwestAngleMethod()
        {
            bool isSolved = false;

            int row = 0, column = 0;
            while (!isSolved)
            {

                isSolved = true;
                for (int i = 0; i < needs.Length; i++)
                {
                    if (needs[i] != 0)
                    {
                        isSolved = false;
                        break;
                    }
                }
            }
        }
        private int findMostPopulatedRow()
        {
            int zeroPotencialRow = 0, max = 0;
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                int sum = 0;
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[i, j].metNeeds > 0)
                    {
                        sum++;
                    }
                }
                if (i == 0)
                {
                    max = sum;
                }
                if (i > 1 && sum > max)
                {
                    zeroPotencialRow = i;
                    max = sum;
                }
            }
            return zeroPotencialRow;
        }
        private void calcPotencials()
        {
            for (int i = 0; i < u.Length; i++)
            {
                u[i] = int.MinValue;
            }
            for (int i = 0; i < v.Length; i++)
            {
                v[i] = int.MinValue;
            }
            int zeroPotencialRow = findMostPopulatedRow();
            u[zeroPotencialRow] = 0;
            bool isSolved = false;
            while (!isSolved)
            {
                for (int i = 0; i < consumers.GetLength(0); i++)
                {
                    for (int j = 0; j < consumers.GetLength(1); j++)
                    {
                        if (consumers[i, j].metNeeds == 0) continue;

                        if (v[j] == int.MinValue && u[i] != int.MinValue)
                        {
                            v[j] = consumers[i, j].transportationCosts - u[i];
                        }
                        else if (u[i] == int.MinValue && v[j] != int.MinValue)
                        {
                            u[i] = consumers[i, j].transportationCosts - v[j];
                        }
                    }
                }
                isSolved = true;
                for (int i = 0; i < u.Length; i++)
                {
                    if (u[i] == int.MinValue)
                    {
                        isSolved = false;
                        break;
                    }
                }
                if (isSolved)
                {
                    for (int i = 0; i < v.Length; i++)
                    {
                        if (v[i] == int.MinValue)
                        {
                            isSolved = false;
                            break;
                        }
                    }
                }
            }
        }
        private void calcDeltas()
        {
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    consumers[i, j].sign = u[i] + v[j] - consumers[i, j].transportationCosts;
                }
            }
        }
        private bool findMaxDelta(out int row, out int column)
        {
            bool isSolved = true;
            int maxDelta = -1;
            row = -1; column = -1;
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    if (consumers[i, j].sign > 0)
                    {
                        isSolved = false;
                        if (maxDelta == -1)
                        {
                            maxDelta = consumers[i, j].sign;
                            row = i;
                            column = j;
                        }
                        else if (consumers[i, j].sign >= maxDelta)
                        {
                            maxDelta = consumers[i, j].sign;
                            row = i;
                            column = j;
                        }
                    }
                }
            }
            return isSolved;
        }
        private Direction calcDirections(int row, int column, Direction forbidden = Direction.None)
        {
            Direction acceptable = Direction.None;

            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                if (i == row) continue;
                if (consumers[i, column].metNeeds > 0)
                {
                    if (i < row)
                    {
                        acceptable.Add(Direction.Up);
                        i = row;
                    }
                    else
                    {
                        acceptable.Add(Direction.Down);
                        break;
                    }
                }
            }

            for (int j = 0; j < consumers.GetLength(1); j++)
            {
                if (j == column) continue;

                if (consumers[row, j].metNeeds > 0)
                {
                    if (j < column)
                    {
                        acceptable.Add(Direction.Left);
                        j = column;
                    }
                    else
                    {
                        acceptable.Add(Direction.Right);
                        break;
                    }
                }
            }
            acceptable.Remove(forbidden);
            return acceptable;
        }
        private Vertex findNextVertex(Vertex vertex)
        {
            if (vertex.AcceptableDirections == Direction.None)
            {
                throw new Exception("Немає допустимих напрямків");
            }
            if (vertex.AcceptableDirections.Contains(Direction.Up))
            {
                for (int i = vertex.Row - 1; i >= 0; i--)
                {
                    if (consumers[i, vertex.Column].metNeeds > 0)
                    {
                        vertex.AcceptableDirections.Remove(Direction.Up);
                        return new Vertex(i, vertex.Column, calcDirections(i, vertex.Column, forbidden: Direction.Down));
                    }
                }
            }
            else if (vertex.AcceptableDirections.Contains(Direction.Down))
            {
                for (int i = vertex.Row + 1; i <= consumers.GetLength(0); i++)
                {
                    if (consumers[i, vertex.Column].metNeeds > 0)
                    {
                        vertex.AcceptableDirections.Remove(Direction.Down);
                        return new Vertex(i, vertex.Column, calcDirections(i, vertex.Column, forbidden: Direction.Up));
                    }
                }
            }
            else if (vertex.AcceptableDirections.Contains(Direction.Left))
            {
                for (int j = vertex.Column - 1; j >= 0; j--)
                {
                    if (consumers[vertex.Row, j].metNeeds > 0)
                    {
                        vertex.AcceptableDirections.Remove(Direction.Left);
                        return new Vertex(vertex.Row, j, calcDirections(vertex.Row, j, forbidden: Direction.Right));
                    }
                }
            }
            else //Right
            {
                for (int j = vertex.Column + 1; j <= consumers.GetLength(1); j++)
                {
                    if (consumers[vertex.Row, j].metNeeds > 0)
                    {
                        vertex.AcceptableDirections.Remove(Direction.Right);
                        return new Vertex(vertex.Row, j, calcDirections(vertex.Row, j, forbidden: Direction.Left));
                    }
                }
            }
            return new Vertex(-1, -1, Direction.None); //Щоб забрати warning
        }
        private void removeUnnecessaryVertices(List<Vertex> cycleVertices)
        {
            for (int i = 2; i < cycleVertices.Count; i++)
            {
                bool rowsMatched = cycleVertices[i].Row == cycleVertices[i - 1].Row && cycleVertices[i - 1].Row == cycleVertices[i - 2].Row;
                bool columnsMatched = cycleVertices[i].Column == cycleVertices[i - 1].Column && cycleVertices[i - 1].Column == cycleVertices[i - 2].Column;
                if (rowsMatched || columnsMatched)
                {
                    // Знайдено три однакових значення підряд
                    // Видалення середнього елемента
                    int indexToRemove = i - 1;
                    cycleVertices.RemoveAt(indexToRemove);
                    // Зменшення лічильника циклу, щоб продовжити перевірку
                    //!!!!!!!!!!!!!!!!!!!
                    //i = 2;
                    i--;
                }
            }
            //останній може бути в одному рядку/стовпці з передостанній і першим
            if (cycleVertices.Last().Row == cycleVertices.ElementAt(cycleVertices.Count - 2).Row && cycleVertices.Last().Row == cycleVertices.First().Row)
            {
                cycleVertices.RemoveAt(cycleVertices.Count - 1);
            }
            else if (cycleVertices.Last().Column == cycleVertices.ElementAt(cycleVertices.Count - 2).Column && cycleVertices.Last().Column == cycleVertices.First().Column)
            {
                cycleVertices.RemoveAt(cycleVertices.Count - 1);
            }
        }
        private List<Vertex> buildCycle(int row, int column)
        {
            bool isSolved = false;
            List<Vertex> cycleVertices = new List<Vertex>();
            int oldVal = consumers[row, column].metNeeds;
            consumers[row, column].metNeeds = int.MaxValue;
            cycleVertices.Add(new Vertex(row, column, calcDirections(row, column)));

            while (!isSolved)
            {
                while (cycleVertices.Last().AcceptableDirections == Direction.None)
                {
                    cycleVertices.Remove(cycleVertices.Last());
                    if (cycleVertices.Count == 0)
                    {
                        Console.WriteLine("ERORRRRRRRRR 1");
                        Environment.Exit(1);
                    }
                }
                Vertex possibleNext = findNextVertex(cycleVertices.Last());
                if (possibleNext.Equals(cycleVertices.First()))
                {
                    isSolved = true;
                    consumers[row, column].metNeeds = oldVal;
                }
                else if (possibleNext.AcceptableDirections != Direction.None)
                {
                    cycleVertices.Add(possibleNext);
                }
            }
            removeUnnecessaryVertices(cycleVertices);
            return cycleVertices;
        }
        private bool checkForDegeneracy()
        {
            int count = 0;
            foreach (Consumer consumer in consumers)
            {
                if (consumer.metNeeds != 0)
                {
                    count++;
                }
            }
            return count != consumers.GetLength(0) + consumers.GetLength(1) - 1;
        }
        private void recalculateTransportation(List<Vertex> cycleVertices)
        {
            int min = -1;
            for (int i = 1; i < cycleVertices.Count; i++)
            {
                if (i % 2 == 0) continue;
                int currentRow = cycleVertices[i].Row;
                int currentColumn = cycleVertices[i].Column;
                if (i == 1)
                {
                    min = consumers[currentRow, currentColumn].metNeeds;
                }
                else if (consumers[currentRow, currentColumn].metNeeds < min)
                {
                    min = consumers[currentRow, currentColumn].metNeeds;
                }
            }

            for (int i = 0; i < cycleVertices.Count; i++)
            {
                int currentRow = cycleVertices[i].Row;
                int currentColumn = cycleVertices[i].Column;
                if (consumers[currentRow, currentColumn].metNeeds == FICTITIOUS_FILLING)
                {
                    consumers[currentColumn, currentColumn].metNeeds = 0;
                }
                if (i % 2 == 0)
                {
                    consumers[currentRow, currentColumn].metNeeds += min;
                }
                else
                {
                    consumers[currentRow, currentColumn].metNeeds -= min;
                }
            }
        }
        private (int, int) fillMin()
        {
            int row = -1, column = -1;
            if (u[0] == int.MinValue)
            {
                int min = -1;
                for (int i = 0; i < consumers.GetLength(0); i++)
                {
                    for (int j = 0; j < consumers.GetLength(1); j++)
                    {
                        if (consumers[i, j].metNeeds != 0) continue;

                        if (min == -1 || consumers[i, j].transportationCosts < min)
                        {
                            min = consumers[i, j].transportationCosts;
                            row = i;
                            column = j;
                        }
                    }
                }
            }
            else
            {
                int max = -1;
                for (int i = 0; i < consumers.GetLength(0); i++)
                {
                    for (int j = 0; j < consumers.GetLength(1); j++)
                    {
                        if (consumers[i, j].metNeeds != 0) continue;

                        if (max == -1 || consumers[i, j].sign > max)
                        {
                            max = consumers[i, j].sign;
                            row = i;
                            column = j;
                        }
                    }
                }
            }
            consumers[row, column].metNeeds = FICTITIOUS_FILLING;
            return (row, column);
        }
        private void fixMin(int row, int column)
        {
            if (row == -1 || column == -1) return;
            consumers[row, column].metNeeds = 0;
        }
        public void Solve()
        {
            minimumElementMethod();
            // printArr();
            // bool t = checkForDegeneracy();
            bool isSolved = false;
            int iter = 0;
            while (!isSolved)
            {
                bool isDegenerated = checkForDegeneracy();
                int minRow = -1, minColumn = -1;
                if (isDegenerated)
                {
                    /*
                    Console.WriteLine("План виродженаий, можливо не кiнцевий розвязок");
                    int currentSum = 0;
                    for (int i = 0; i < consumers.GetLength(0); i++)
                    {
                        for (int j = 0; j < consumers.GetLength(1); j++)
                        {
                            currentSum += consumers[i, j].transportationCosts * consumers[i, j].metNeeds;
                        }
                    }
                    Console.WriteLine($"SUM = {currentSum}");
                    Environment.Exit(2);
                    */
                    (minRow, minColumn) = fillMin();
                }
                calcPotencials();
                calcDeltas();
                isSolved = findMaxDelta(out int row, out int column);
                if (isSolved)
                {
                    fixMin(minRow, minColumn);
                    break;
                }
                var cycleVertices = buildCycle(row, column);
                fixMin(minRow, minColumn);
                recalculateTransportation(cycleVertices);
                printArr();
                Console.WriteLine();
                Console.WriteLine();
            }

            int sum = 0;
            for (int i = 0; i < consumers.GetLength(0); i++)
            {
                for (int j = 0; j < consumers.GetLength(1); j++)
                {
                    sum += consumers[i, j].transportationCosts * consumers[i, j].metNeeds;
                }
            }
            Console.WriteLine($"SUM = {sum}");
        }
    }
}