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.
コード:
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