#include #define pb push_back #define FOR(i, a, b) for(int i = a; i < b; i++) //#define FOR(i, a) FOR(i, 0, a) #define st first #define nd second //#pragma GCC optimize ("Ofast") //#pragma GCC target("sse, sse2, sse3, sse4, popcnt, abm, mmx, avx, time=native") using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vll; const int MAX = 1000; char A[MAX][MAX]; int B[MAX][MAX]; int C[MAX][MAX]; int R[MAX][MAX]; int main() { ios_base::sync_with_stdio(0); int n, m; cin>>n>>m; for(int i=0; i>A[i][j]; } } ll res = 0; // ### // 1 // ### for(int i=0; i=0; j--) { B[i][j] = 1; if(A[i][j] == A[i][j+1]) B[i][j] += B[i][j+1]; } } for(int j=0; j=0; i--) { C[i][j] = 1; if(A[i][j] == A[i+1][j]) C[i][j] += C[i+1][j]; } } int j; for(int i=n-1; i>=0; i--) { j = m-1; char c = A[i][m-1]; int r = 1; R[i][m-1] = 0; int r2; for(int k=0; i-k >= 0; k++) { if(A[i-k][j-k] == c) { r2 = min(B[i-k][j-k], C[i-k][j-k]); if(r2 >= r + 2) r += 2; else r = min(2, r2); //cout<<" "<=0; j--) { i = n-1; char c = A[i][j]; int r = 1; R[i][j] = 0; int r2; for(int k=0; i-k >= 0 && j-k >= 0; k++) { if(A[i-k][j-k] == c) { r2 = min(B[i-k][j-k], C[i-k][j-k]); if(r2 >= r + 2) r += 2; else r = min(2, r2); //cout<<" "<= r + 2) r += 2; else r = min(2, r2); } else { c = A[i+k][j+k]; r = min(B[i+k][j+k], C[i+k][j+k]); r = min(2, r); } R[i+k][j+k] = r; res += (r-1); } } for(j = 1; j= 0 && j-k >= 0; k++) { if(A[i+k][j+k] == c) { r2 = min(B[i+k][j+k], C[i+k][j+k]); if(r2 >= r + 2) r += 2; else r = min(2, r2); } else { c = A[i+k][j+k]; r = min(B[i+k][j+k], C[i+k][j+k]); r = min(2, r); } R[i+k][j+k] = r; res += (r-1); } } // ### // 3 // ### for(i=0; i=0; i--) { C[i][j] = 1; if(A[i][j] == A[i+1][j]) C[i][j] += C[i+1][j]; } } for(i=0; i= r + 2) r += 2; else r = min(2, r2); } else { c = A[i-k][j+k]; r = min(B[i-k][j+k], C[i-k][j+k]); r = min(2, r); } R[i-k][j+k] = r; res += (r-1); } } for(j = 1; j= r + 2) r += 2; else r = min(2, r2); } else { c = A[i-k][j+k]; r = min(B[i-k][j+k], C[i-k][j+k]); r = min(2, r); } R[i-k][j+k] = r; res += (r-1); } } // ### // 4 // ### for(i=0; i=0; j--) { B[i][j] = 1; if(A[i][j] == A[i][j+1]) B[i][j] += B[i][j+1]; } } for(j=0; j= r + 2) r += 2; else r = min(2, r2); } else { c = A[i+k][j-k]; r = min(B[i+k][j-k], C[i+k][j-k]); r = min(2, r); } R[i+k][j-k] = r; res += (r-1); } } for(j = m-2; j>=0; j--) { i = 0; char c = A[i][j]; int r = 1; R[i][j] = 0; int r2; for(int k=0; i+k < n && j-k < m; k++) { if(A[i+k][j-k] == c) { r2 = min(B[i+k][j-k], C[i+k][j-k]); if(r2 >= r + 2) r += 2; else r = min(2, r2); } else { c = A[i+k][j-k]; r = min(B[i+k][j-k], C[i+k][j-k]); r = min(2, r); } R[i+k][j-k] = r; res += (r-1); } } cout<