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

### 题目描述

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

## Description

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

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

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

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

## 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;
}
``````