题目
link
题解
悬线法
正方形最大面积可以统计最大变成的平方
最大边长等于min(r[i][j] - l[i][j] + 1, h[i][j])
锅
当i==1时候l与r数组不要更新。。。。。
代码
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
76
77
78
79
| #include<bits/stdc++.h>
using namespace std;
const int N = 2100;
int M[N][N];
int zhuan[N][N];
int n, m;
int h[N][N], l[N][N], r[N][N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> M[i][j];
h[i][j] = 1;
l[i][j] = r[i][j] = j;
}
}
for(int i = 2;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(M[i - 1][j] != M[i][j])
{
h[i][j] = h[i - 1][j] + 1;
}
}
}
for(int i = 1;i <= n;i++)
{
for(int j = 2;j <= m;j++)
{
if(M[i][j - 1] != M[i][j])
{
l[i][j] = l[i][j - 1];
}
}
}
for(int i = 1;i <= n;i++)
{
for(int j = m - 1;j >= 1;j--)
{
if(M[i][j + 1] != M[i][j])
{
r[i][j] = r[i][j + 1];
}
}
}
int maxsquare = 0;
int maxlen = 0;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
if(M[i - 1][j] != M[i][j])
{
if(i == 1) continue;
l[i][j] = max(l[i][j], l[i - 1][j]);
r[i][j] = min(r[i][j], r[i - 1][j]);
}
int b = min(r[i][j] - l[i][j] + 1, h[i][j]);
maxlen = max(maxlen, b * b);
maxsquare = max(maxsquare, (r[i][j] - l[i][j] + 1) * h[i][j]);
}
}
cout << maxlen << endl;
cout << maxsquare << endl;
return 0;
}
|