9度ブラシ問題

1932 ワード

タイトルの説明:
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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 2010
int h[MAXN],r[MAXN],l[MAXN];
int map[MAXN][MAXN];
char str[2];
int n,m;
void all_1_matrix()
{
    int i,j,max = 0;
    memset(h,0,sizeof(h));
    for(i = 0; i < n; i++)
    {
        for(j = 0 ; j < m; j++)
        {
            if(map[i][j] == 1)
                h[j] ++;
            else h[j] = 0;
        }
        //  
        // left  h〔j〕 
        for(j = 0; j < m; j ++)
        {
            l[j] = j;
            while(l[j] > 0 && h[j] <= h[l[j] - 1])
                l[j] = l[l[j] - 1];
        }
        // right h〔j〕 
        for(j = m-1; j >= 0; j --)
        {
            r[j] = j;
            while(r[j] < m-1 && h[j] <=h[r[j] + 1])
                r[j] = r[r[j] + 1];
        }
        for(j = 0; j < m; j ++)
        {
            if((r[j] - l[j] + 1) * h[j] > max)
                max = (r[j] - l[j] + 1) * h[j];
        }
    }
    printf("%d
",max); } int main() { int t, i , j, k, len ; char ch; while(scanf("%d %d",&n,&m)!=EOF) { // scanf("%d %d",&n,&m); for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { scanf("%d",&map[i][j]); } } all_1_matrix(); } }