4630: 【GESP2406五级】黑白格

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

⼩杨有⼀个$n$ 行$m$ 列的网格图，其中每个格子要么是白色，要么是黑色。
小杨想知道至少包含$k$ 个黑色格子的最小子矩形包含了多少个格子。

输入

第一行包含三个正整数$n,m,k$ ，含义如题面所示。
之后$n$ 行，每行一个长度为$m$ 的$01$ 串，代表网格图第$i$ 行格子的颜色，如果为$0$ ，则对应格子为白色，否则为黑色。

输出

输出一个整数，代表至少包含$k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出$0$ 。

样例输入 复制 

4 5 5
00000
01111
00011
00011

样例输出 复制 

6

提示

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int w[N][N];
int sum[N][N];
int n, m;
int main() {
    int k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            w[i][j] = s[j - 1] - '0';
            sum[i][j] = sum[i][j - 1] + w[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = i; j <= m; j++) {
            vector < int > num;
            int now = 0;
            for (int l = 1; l <= n; l++) {
                int tmp = sum[l][j] - sum[l][i - 1];
                now += tmp;
                num.push_back(now);
                if (now >= k) {
                    if (ans == 0) ans = (j - i + 1) * l;
                    else ans = min(ans, (j - i + 1) * l);
                    int L = 1, R = l;
                    while (L < R) {
                        int mid = L + R + 1 >> 1;
                        if (now - num[mid - 1] >= k) L = mid;
                        else R = mid - 1;
                    }
                    if (now - num[L - 1] >= k) {
                        if (ans == 0) ans = (j - i + 1) * (l - L);
                        else ans = min(ans, (j - i + 1) * (l - L));
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

来源/分类

提交提交记录统计露一手!