01マトリクス最大正方形

2122 ワード

【タイトル説明】
1つのR行C列の01行列を与えて、1つの最大の正方形の全1のサブ行列を求めて、そしてこの最大の正方形のサブ行列の面積を出力します.
【入力】
第1行は2つの正の整数R,Cを与え、行列がR行C列であることを示す.
次に、R行C列は、隣接する2つの要素が1つのスペースで区切られたこの01行列を与える.
【出力】
1つの数、最大正方形サブマトリクスの面積(すなわち1の数).
入出力サンプル】
matrix.in
matrix.out
5 8 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0 1
9  
【データ範囲制限】
20%のデータ、R、C<=20;
40%のデータ、R、C<=100;
100%のデータ、R、C<=1000.
コード:
        #region  01       
        public void GetMaxMatrix()
        {
            StreamReader sr = File.OpenText("matrix.in");
            StreamWriter sw = File.CreateText("matrix.out");
            string[] str = sr.ReadLine().Split(" ".ToCharArray());
            int R = int.Parse(str[0]);
            int C = int.Parse(str[1]);
            int[,] matrix = new int[R, C];
            matrix = new int[R, C];
            string strLine = null;
            int i = 0;
            while ((strLine = sr.ReadLine()) != null)
            {
                str = strLine.Split(" ".ToCharArray());
              
                    for (int j = 0; j < C; j++)
                    {
                        matrix[i, j] = int.Parse(str[j]);
                    }
                    i++;
            }
            int max = 1;
      
            for ( i = 1; i < R; i++)
                for (int j = 1; j < C; j++)
                    if (matrix[i, j] == 1)
                    {
                        int mmin = min(matrix[i - 1, j], matrix[i, j - 1]);
                        mmin = min(matrix[i - 1, j - 1], mmin);
                        matrix[i, j] = mmin + 1;
                        if (max < matrix[i, j])
                            max = matrix[i, j];
                      
                       
                    }
            sw.WriteLine(max);
            sw.Flush();
            sw.Close();
            sr.Close();
        }
        #endregion
        #region     
        int min(int a, int b)
        {
            return a < b ? a : b;
        }
        #endregion