NC17499. Sudoku Subrectangles
描述
输入描述
The first line of input contains two space-separated integers n, m (1 ≤ n, m ≤ 1000).
The next n lines contain m characters each, denoting the characters of the grid. Each character is an English letter (which can be either uppercase or lowercase).
输出描述
Output a single integer, the number of sudoku-like subrectangles.
示例1
输入:
2 3 AaA caa
输出:
11
说明:
For simplicity, denote the j-th character on the i-th row as (i, j).示例2
输入:
4 5 abcde fGhij klmno pqrst
输出:
150
说明:
For sample 2, the grid has 150 nonempty subrectangles, and all of them are sudoku-like.C++14(g++5.4) 解法, 执行用时: 366ms, 内存消耗: 9432K, 提交时间: 2018-08-10 14:34:07
#include<bits/stdc++.h>
using namespace std;
char s[1005][1005];
int pos[1005];
int l[1005][1005];
int u[1005][1005];
int len[1005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>s[i][j];
for(int i=1;i<=n;i++){
memset(pos,0,sizeof(pos));
for(int j=1;j<=m;j++){
l[i][j]=min(l[i][j-1]+1,j-pos[s[i][j]]);
pos[s[i][j]]=j;
}
}
for(int j=1;j<=m;j++){
memset(pos,0,sizeof(pos));
for(int i=1;i<=n;i++){
u[i][j]=min(u[i-1][j]+1,i-pos[s[i][j]]);
pos[s[i][j]]=i;
}
}
long long ans=0;
for(int j=1;j<=m;j++){
memset(len,0,sizeof(len));
for(int i=1;i<=n;i++){
for(int k=0;k<l[i][j];k++){
len[k]=min(len[k]+1,u[i][j-k]);
if(k) len[k]=min(len[k],len[k-1]);
ans+=len[k];
}
for(int k=l[i][j];k<54;k++)len[k] =0;
}
}
cout<<ans<<"\n";
}
C++ 解法, 执行用时: 148ms, 内存消耗: 9268K, 提交时间: 2021-10-07 15:44:51
#include <bits/stdc++.h>
#define fp(i, a, b) for(int i = a, i##_ = (b) + 1; i < i##_; ++i)
using namespace std;
const int N = 1e3 + 5;
char s[N][N];
int L[N][N],U[N][N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
fp(i, 1, n) {
scanf("%s", s[i] + 1);
vector<int> pos(256);
fp(j, 1, m) L[i][j] = min(L[i][j - 1] + 1, j - pos[s[i][j]]), pos[s[i][j]] = j;
}
fp(j, 1, m) {
vector<int> pos(256);
fp(i, 1, n) U[i][j] = min(U[i - 1][j] + 1, i - pos[s[i][j]]), pos[s[i][j]] = i;
}
int64_t ans = 0;
fp(j, 1, m){
vector<int> h(53);
fp(i, 1, n) {
fp(k, 0, L[i][j] - 1)
ans += h[k] = min({h[k] + 1, U[i][j - k], k ? h[k - 1] : n});
fp(k, L[i][j], 52) h[k] = 0;
}
}
printf("%lld\n", ans);
return 0;
}