D. Rarity and New Dress
题意
给出一个n*m的矩阵
每个位置被染成不同的颜色
问这个矩阵能取出多少个的相同颜色组成的斜正方形
(一个矩阵可以反复使用每次只取出一个斜正方形)
题解:
以某个点为中心不断延伸扩大,发现以它为中心的斜正方形共有r(i,j)个
定义r(i,j)表示以第i行第j列为中心点形成的斜正方形的最大半径
那么这个矩阵能形成共ans个菱形:
应为以每个点为中心辐射延伸的图形不会与以其他点为中心的辐射延伸重叠
所以不会产生重复统计
那么只要找到每个点对应的半径就能暴力求解出答案
对于矩阵中寻找某种特定图案构成的区域不妨考虑将图形”切片” 或 “分解”
从四个方向进行dp
设置L(i,j),R(i,j),U(i,j),D(i,j) 对于每一行维护L(i,j)与R(i,j) 即以(i,j)为端点向左/右延伸同种颜色最长的连续区间
利用一个中间变量mid(i,j)=min(L(i,j),R(i,j))找到以(i,j)为对称中心的最长半径，
这步可以抽象成将图形横向“切片”
更新U(i,j)若(i,j)与(i-1,j)颜色相同U(i,j)=min(U(i-1,j)+1,mid(i,j))否则U(i,j)=1
更新D(i,j)若(i,j)与(i+1,j)颜色相同D(i,j)=min(D(i+1,j)+1,mid(i,j))否则D(i,j)=1
这步是将每一层的”切片”摞在一起修成一个上三角和下三角
然后对于每个点的r(i,j)=min(U(i,j),D(i,j)) 一个菱形也就是斜正方形它是由上下两个对称的三角形组成
所以上三角与下三角中取小的尺寸组成的菱形是以(i,j)为中心的最大菱形
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e3+5;
const double Pi=acos(-1);
string s[Max];
int l[Max][Max],r[Max][Max];
ll up[Max][Max],down[Max][Max],mid[Max][Max];
int main(){
Turnoff;
int n,m;cin>>n>>m;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++){
//l[i][0]=1,r[i][m-1]=1;
for(int j=0;j<m;j++){
if(j>0&&s[i][j]==s[i][j-1])l[i][j]=l[i][j-1]+1;
else l[i][j]=1;
}
for(int j=m-1;j>=0;j--){
if(j<m-1&&s[i][j]==s[i][j+1])r[i][j]=r[i][j+1]+1;
else r[i][j]=1;
}
for(int j=0;j<m;j++)mid[i][j]=min(l[i][j],r[i][j]);
}
for(int i=n-1;i>=0;i--){
for(int j=0;j<m;j++){
if(i<n-1&&s[i+1][j]==s[i][j])down[i][j]=min(mid[i][j],down[i+1][j]+1);
else down[i][j]=1;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
//cout<<l[i][j]<<" "<<r[i][j]<<" "<<mid[i][j]<<endl;
if(i>0&&s[i][j]==s[i-1][j])up[i][j]=min(mid[i][j],up[i-1][j]+1);
else up[i][j]=1;
}
}
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
//cout<<up[i][j]<<" "<<down[i][j]<<endl;
ans+=min(up[i][j],down[i][j]);
}
}
cout<<ans<<endl;
}
|