Skip to content

11074: 【原1074】LSZ的雪地脚印

题目

题目描述

author: oldherl 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1074

Description

2006年冬的某一天上午下了一场大雪,TSYZ教学楼下的排球场上覆盖了一层雪。

下课了,很多人来到这里,留下了很多脚印。

排球场可以看作是由N×M的方格组成的一个矩形, 其中某些方格已经有脚印了,而剩下的则是完好的。

lsz想在上面写下自己的名字,也就是"lsz"三个字母,为了美观,要求这三个字母必须占据一个2:1(横向的,不能是1:2)的完好矩形,

也就是说,在这个2:1的矩形内不得有脚印。

现在给你场地的脚印情况,lsz想知道自己的名字最大可以占据多大面积。

40%的数据满足N,M<123

100%的数据满足0<N,M<1234

Input Format

第一行为空格分隔的两个正整数,N和M,表示场地的大小。

下面有N行,每行M个字符,每个字符要么是-(减号),表示该方格完好,要么是X(大写的x),表示该方格有脚印。

Output Format

一个正整数,表示"lsz"最大可以占据多大面积。

Hint

来源:2008年TSOI第一次模拟赛

样例解释 占据第二行和第三行的前4个方格。

Sample Input

4 6
X--XXX
----X-
------
-X--X-

Sample Output

8

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/28.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

bool table[2600][1300];
int dp[2600][1300];

int main() {
    int n, m;
    char tmp;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            do {
                scanf("%c", &tmp);
            } while (tmp == '\n');
            table[2 * i - 1][j] = tmp == '-';
            table[2 * i][j] = tmp == '-';
        }
    }

    int maxAns = 0;

    for (int i = 1; i <= 2 * n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (table[i][j]) {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                maxAns = max(dp[i][j], maxAns);
            }
        }
    }

    maxAns = maxAns / 2 * 2;
    cout << maxAns * maxAns / 2 << endl;
    return 0;
}

FineArtz's solution

/* LSZ的雪地脚印 */
#include <iostream>
#include <cstring>
using namespace std;

int a[1235][1235], s[1235][1235], f[1235][1235];

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            char ch;
            cin >> ch;
            a[i][j] = (ch == 'X' ? 1 : 0);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i){
        for (int j = 2; j <= m; ++j){
            if (a[i][j])
                continue;
            for (int t = f[i - 1][j] + 1; t >= 1; --t){
                int x = i - t + 1, y = j - 2 * t + 1;
                if (x <= 0 || y <= 0)
                    continue;
                int p = s[i][j] - s[x - 1][j] - s[i][y - 1] + s[x - 1][y - 1];
                if (p == 0){
                    f[i][j] = t;
                    break;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= m; ++j)
            if (f[i][j] > ans)
                ans = f[i][j];
    cout << ans * ans * 2 << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

bool ground[1240][1240] = { 0 };
int sum[1240][1240] = { 0 };

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; ++i) {
        sum[i][0] = sum[i - 1][1];
        for (int j = 1; j <= M; ++j) {
            while (true) {
                char c;
                scanf("%c", &c);
                if (c == 'X') {
                    ground[i][j] = true;
                    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + 1;
                    break;
                }
                else if (c == '-') {
                    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
                    break;
                }
            }
        }
    }

    int cur_max = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = cur_max * 2; j <= M; ++j) {
            for (int k = cur_max; j >= k * 2 && i >= k; ++k) {
                if (sum[i][j] - sum[i][j - k * 2] - sum[i - k][j] + sum[i - k][j - k * 2] == 0) {
                    cur_max = k;
                }
                else
                    break;
            }
        }
    }

    cout << cur_max * cur_max * 2;

    return 0;
}

skyzh's solution

#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

int MAP[2001][2001] = { 0 };
int D[2001][2001] = { 0 };

int main() {
    int M, N;
    char tmp;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> tmp;
            if (tmp == 'X') MAP[i][j] = 1;
            else MAP[i][j] = 0;
        }
    }
    D[1][1] = MAP[1][1];
    for (int j = 2; j <= M; j++) D[1][j] = D[1][j - 1] + MAP[1][j];
    for (int i = 2; i <= N; i++) {
        D[i][1] = MAP[i][1] + D[i - 1][1];
        for (int j = 2; j <= M; j++) {
            D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + MAP[i][j];
        }
    }
    int L = 0, R = min(N, M);
    while (L < R) {
        int S = (L + R + 1) / 2;
        int S2 = S * 2;
        bool ok = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (i + S > N || j + S2 > M) continue;
                int cnt = D[i + S][j + S2] - D[i][j + S2] - D[i + S][j] + D[i][j];
                if (cnt == 0) {
                    ok = true;
                    break;
                }
            }
            if (ok) break;
        }
        if (ok) L = S; else R = S - 1;
    }
    cout << L * L * 2 << endl;
    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
char map[1500][1500];
int m,n,d,ans,h[1500],l[1500],r[1500],curl,curr;
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for (int i=0;i<m;++i)
        for (int j=0;j<n;++j)
            cin>>map[i][j];
    for (int i=0;i<n;++i) r[i]=n-1;
    for (int i=0;i<m;++i){
        for (int j=0;j<n;++j)
            if (map[i][j]=='-') h[j]++;
            else h[j]=0;
        curl=0;
        for (int j=0;j<n;++j)
            if (map[i][j]=='-') l[j]=max(curl,l[j]);
            else {l[j]=0; curl=j+1;}
        curr=n-1;
        for (int j=n-1;j>=0;--j) {
            if (map[i][j] == '-') r[j] = min(curr, r[j]);
            else {r[j] = n-1; curr=j-1;}
            d=min((r[j]-l[j]+1)/2,h[j]);
            if (2*d*d>ans) ans=2*d*d;
        }
    }
    cout<<ans;
}

yyong119's solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

int map[1250][1250], cnt[1250][1250];
int maxS = 0;

int main() {

    ios::sync_with_stdio(false);
    int w, l;
    cin >> w >> l;
    char tmp;
    for (int i = 1; i <= w; ++i)
        for (int j = 1; j <= l; ++j) {
            cin >> tmp;
            if (tmp == 'X') map[i][j] = 1;
            cnt[i][j] = map[i][j] + cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
        }
    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < l; ++j) {
            if (map[i + 1][j + 1]) continue;
            int xr = w - i, yr = l - j;
            if (xr <= maxS || (yr >> 1) <= maxS) continue;
            // //横向     //又踩坑了这个要用二分二分二分!!!
            // int Hmax = min(yr / 2, xr);
            // for (int p = Hmax; p > maxS; --p)
            //  if (cnt[i][j + p * 2] + cnt[i + p][j] - cnt[i][j] == cnt[i + p][j + 2 * p]) {
            //      maxS = p;
            //      break;
            //  }
            int r = min(yr / 2, xr), l = 1, mid;
            while (l < r) {
                mid = (l + r + 1) / 2;
                if (cnt[i][j + mid * 2] + cnt[i + mid][j] - cnt[i][j] == cnt[i + mid][j + 2 * mid])
                    l = mid;
                else r = mid - 1;
                // cout << l << mid << r << endl;
            }
            if (cnt[i][j + mid * 2] + cnt[i + mid][j] - cnt[i][j] != cnt[i + mid][j + 2 * mid]) mid--;
            if (mid > maxS) maxS = mid;
            //纵向            //哎哟注意看题目啊不能纵向的  
            // int Vmax = min(yr, xr / 2);
            // for (int p = Vmax; p > maxS; --p)
            //  if (cnt[i][j + p] + cnt[i + 2 * p][j] - cnt[i][j] == cnt[i + 2 * p][j + p]) {
            //      maxS = p;
            //      break;
            //  }
        }
    }
    cout << maxS * maxS * 2 << endl;
    return 0;
}