ダイナミックプランニング-最大面積の全1サブマトリクス
1925 ワード
タイトルの説明:
1つのM*Nの行列の中で、すべての要素は0と1だけで、この行列の中から1つの面積の最大の全1サブ行列を探し出して、いわゆる最大は要素1の個数が最も多いことを指します.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される最初の行は2つの整数m、n(1<=m、n<=1000):入力するマトリクスのサイズを表します.行列にはm行があり、各行にはn個の整数があり、それぞれ0または1であり、隣接する2つの数の間に厳密に1つのスペースで区切られている.
出力:
各テストケースに対応して、出力マトリクスの中で面積が最も大きい全1サブマトリクスの要素数.
サンプル入力:
サンプル出力:
1つのM*Nの行列の中で、すべての要素は0と1だけで、この行列の中から1つの面積の最大の全1サブ行列を探し出して、いわゆる最大は要素1の個数が最も多いことを指します.
入力:
入力には、複数のテストサンプルが含まれる場合があります.各テストケースについて、入力される最初の行は2つの整数m、n(1<=m、n<=1000):入力するマトリクスのサイズを表します.行列にはm行があり、各行にはn個の整数があり、それぞれ0または1であり、隣接する2つの数の間に厳密に1つのスペースで区切られている.
出力:
各テストケースに対応して、出力マトリクスの中で面積が最も大きい全1サブマトリクスの要素数.
サンプル入力:
2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
サンプル出力:
0
4
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int mat[1010][1010];
int h[1010]; //
int l[1010]; // ,
int r[1010]; //
int main()
{
int n, m;
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) == 2)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &mat[i][j]);
}
}
memset(h, 0, sizeof(h));
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (mat[i][j] == 1)
{
h[j]++;
}
else
{
h[j] = 0;
}
}
h[0] = h[m + 1] = -1;
//l[j] : h[j]
for (int j = 1; j <= m; j++)
{
int k = j; // k
while (h[j] <= h[k - 1]){
k = l[k - 1]; // , k , k 。
}
l[j] = k;
}
// for (int j = 1; j <= m; j++)
// {
// cout << l[j] << " ";
// }
// cout << endl ;
for (int j = m; j >= 1; j--)
{
int k = j;
while (h[j] <= h[k + 1])
k = r[k + 1];
r[j] = k;
}
// for (int j = 1; j <= m; j++)
// {
// cout << r[j] << " ";
// }
// cout << endl <<endl;
for (int j = 1; j <= m; j++)
{
if (ans < h[j] * (r[j] - l[j] + 1))
{
ans = h[j] * (r[j] - l[j] + 1);
}
}
}
printf("%d
", ans);
}
return 0;
}