1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
using namespace std;

const int maxN = 800 + 5;
int n, m, k, sum[maxN][maxN];
char  a[maxN][maxN];

void input()
{
    cin >> n >> m >> k;
    for(int r=1; r<=n; r++)
    {
        for(int c=1; c<=m; c++)
        {
            cin >> a[r][c];
        }
    }
}

//求二维数组前缀和
void getPreSum()
{
	for(int r=1; r<=n; r++)
    {
        for(int c=1; c<=m; c++)
        {
            sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1] + (a[r][c] == '.');
        }
    }
}

int getSum(int r1, int c1, int r2, int c2)
{
    return sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1];
}

int main()
{
    //freopen("T5.in", "r", stdin);

    input();
    getPreSum();

    const int INF = 2100000000;
    int minArea = INF;

    for(int r1 = 1; r1 <= n; r1++)
    {
        for(int c1 = 1; c1 <= m; c1++)
        {
            for(int r2 = r1; r2 <= n; r2++)
            {
                for(int c2 = c1; c2 <= m; c2++)
                {
                    if(getSum(r1, c1, r2, c2) >= k && (r2 - r1 + 1) * (c2 - c1 + 1) < minArea)
                    {
                        minArea = (r2 - r1 + 1) * (c2 - c1 + 1);
                    }
                }
            }
        }
    }

    if(minArea == INF)
    {
        cout << "No Solution";
    }
    else
    {
        cout << minArea;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

char seat; //'X'表示已被预订，'.'表示空座
const int maxN = 800 + 10;
int n, m, k, totalEmpty, ans = 1e9, a[maxN][maxN];

void getSectionSum(int L, int R)
{
    int emptySeats = 0, up = 1, down = 1;
    for(; up <= n; up++)
    {
        for(; down <= n && emptySeats < k; down++)
        {
            emptySeats += a[down][R] - a[down][L - 1];
        }

        if(emptySeats < k)
        {
            break;
        }

        //down最后又自加了一次，所以down-up不用再+1
        ans = min(ans,(R - L + 1) * (down - up));
        emptySeats -= a[up][R] - a[up][L - 1];
    }
}

int main()
{
    //freopen("T5.in", "r", stdin);
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>seat;
            totalEmpty += (seat == '.'); //总共有多少个空座
            a[i][j] = a[i][j - 1] + (seat == '.');
        }
    }

    if(totalEmpty < k)
    {
        cout<<"No Solution"<<endl;
        return 0;
    }

    for(int L = 1; L <= n; L++)
    {
        for(int R = L; R <= m; R++)
        {
            getSectionSum(L, R);
        }
    }

    cout<<ans<<endl;

    return 0;
}

1
2
3
了解中小学信息学竞赛请加微信307591841（QQ同号）