/// 111 年工科賽第 5 題
/// 運算對稱矩陣以求出分割值
/// 漆家豪 於海青資訊科 2024/2/11
#define DEBUG
#undef DEBUG
using System;
using System.Numerics;
using System.Text;

class Program
{
    /// <summary>
    /// 讀取檔案資訊存入陣列
    /// </summary>
    /// <param name="fileName">檔案名稱</param>
    /// <returns>取得檔案內容之陣列</returns>
    public static double[,] readFile(string fileName)
    {
        try
        {
            fileName += (fileName.ToUpper().IndexOf(".TXT") >= 0 ? "" : ".TXT");
            string[] lines = File.ReadAllLines("../../../" + fileName);
            int n = lines.Length;
            double[,] matrix = new double[n+1, n+1]; matrix[0, 0] = 1.0;
            for (int i = 1; i <= n; i++)
            {
                string[] values = lines[i-1].Split(' ');
                for (int j = 0; j < values.Length; j++)
                {
                    matrix[i, j] = Convert.ToDouble(values[j]);
                }
            }
            for(int i = 0;i<=n; i++)
            {
                for(int j=0; j<=i; j++)
                {
                    matrix[j, i] = ( i==j ? 1.0 : matrix[i,j] );
                }
            }
            return matrix;
        }
        catch (Exception ex)
        {
            Console.WriteLine($"An error occurred while reading the file: {ex.Message}");
            return null;
        }
    }

    /// <summary>
    /// 陣列遞移律(Transitive closure)運算
    /// </summary>
    /// <param name="n">陣列長度</param>
    /// <param name="matrix">陣列值</param>
    static void transitiveClosure(ref double [,] matrix)
    {
        double minVal, maxVal;
        bool updated = true;
        while (updated)
        {
            updated = false;
            for (int x = 0; x < matrix.GetLength(0); x++)
            {
                for (int y = 0; y < matrix.GetLength(1); y++)
                {
                    if (x != y)
                    {
                        maxVal = int.MinValue;
                        for (int i = 0; i < matrix.GetLength(1); i++)
                        {
                            minVal = Math.Min(matrix[x, i], matrix[i, y]);
                            if (minVal > maxVal)
                            {
                                maxVal = minVal;
                            }
                        }
                        if (maxVal != matrix[x, y])
                        {
                            matrix[x, y] = maxVal;
                            updated = true;
                        }
                    }
                }
            }
        }
    }

    /// <summary>
    /// 取得矩陣上三角每列的極大值
    /// </summary>
    /// <param name="matrix">目標矩陣</param>
    /// <param name="maxRow">上三角每列的極大值存放位置</param>
    static void getMax(double[,] matrix , ref double[] maxRow)
    {
        double max;
        for (int i = 0; i < matrix.GetLength(0); i++)
        {
            max = int.MinValue;
            for (int j = i + 1; j < matrix.GetLength(1); j++)
            {
                if (matrix[i, j] > max)
                {
                    max = matrix[i, j];
                }
            }
            maxRow[i] = max;
        }
    }

    /// <summary>
    /// 輸出陣列內容
    /// </summary>
    /// <param name="matrix">2 維陣列</param>
    static void printMatrix(double[,] matrix)
    {
        for(int i=0; i<matrix.GetLength(0); i++)
        {
            for(int j=0;j<matrix.GetLength(1); j++)
            {
                Console.Write($"{matrix[i, j],6:F2} ");
            }
            Console.WriteLine();
        }
    }

    static void Main(string[] args)
    {
#if DEBUG
        string fileName = "1.txt";
#else
        Console.Write("Enter filename:");
        string fileName = Console.ReadLine();
#endif
        double[,] matrix = readFile(fileName);
        double[] maxRow = new double[matrix.GetLength(0)];
        Console.WriteLine("所輸入的對稱矩陣：");
        printMatrix(matrix);
        transitiveClosure(ref matrix);//步驟一:遞移律運算 (transitive closure)
        Console.WriteLine("\n經過幾次遞移律(Transitive closure)運算後的對稱矩陣：");
        printMatrix(matrix);
        getMax(matrix,ref maxRow);//步驟二:取得陣列右上角每列最大值
        Console.WriteLine("\n對稱矩陣的右上半每列最大值：");
        for (int i = 0; i < maxRow.Length-1; i++) Console.Write($"{maxRow[i]} "); Console.WriteLine();
        Array.Sort(maxRow);//步驟三:排序陣列
        Console.WriteLine("\n對稱矩陣的右上半每列最大值的排序(各值只出現一次)：");
        for (int i = 1; i < maxRow.Length; i++)
        {
            if ((maxRow[i] != maxRow[i-1]))
                Console.Write($"{maxRow[i]} "); 
        }
        Console.WriteLine();
        return;
    }
}