#include using namespace std; typedef unsigned long long int n_t; /*template static void PrintMtx(const vector>& m) { cout << "\n*****************************************" << endl; for (int i = 0; i < m.size(); ++i) { for (int j = 0; j < m[i].size(); ++j) { cout << m[i][j] << ' '; } cout << endl; } }*/ int main() { ios_base::sync_with_stdio(false); string line; getline(cin, line); stringstream ss(line); int n, m; ss >> n >> m; vector> vec(n, vector(m)); for (int i = 0; i < n; ++i) { getline(cin, line); for (int j = 0; j < m; ++j) { vec[i][j] = line[j]; } } vector> dp1(n, vector(m)); vector> dp2(n, vector(m)); vector> dp3(n, vector(m)); vector> dp4(n, vector(m)); // ---------------------- auto s_i = n - 2; auto s_j = m - 2; int c_i, c_j; auto s = 0; while (s_i >= 0 && s_j >= 0) { c_i = s_i; c_j = s_j; while (c_i <= n - 2 && c_j >= 0) { char a = vec[c_i + 1][c_j]; char b = vec[c_i][c_j + 1]; if (a == b && b == vec[c_i][c_j]) { dp1[c_i][c_j] = min(dp1[c_i + 1][c_j], dp1[c_i][c_j + 1]) + 1; s += dp1[c_i][c_j]; } ++c_i; --c_j; } if (s_i > 0) --s_i; else --s_j; } // ---------------------- s_i = 1; s_j = 1; while (s_i < n && s_j < m) { c_i = s_i; c_j = s_j; while (c_i < n && c_j >= 1) { char a = vec[c_i - 1][c_j]; char b = vec[c_i][c_j - 1]; if (a == b && b == vec[c_i][c_j]) { dp2[c_i][c_j] = min(dp2[c_i - 1][c_j], dp2[c_i][c_j - 1]) + 1; s += dp2[c_i][c_j]; } ++c_i; --c_j; } if (s_j < m - 1) ++s_j; else ++s_i; } // ---------------------- s_i = n - 2; s_j = 1; while (s_i >= 0 && s_j < m) { c_i = s_i; c_j = s_j; while (c_i < n - 1 && c_j < m) { char a = vec[c_i + 1][c_j]; char b = vec[c_i][c_j - 1]; if (a == b && b == vec[c_i][c_j]) { dp3[c_i][c_j] = min(dp3[c_i + 1][c_j], dp3[c_i][c_j - 1]) + 1; s += dp3[c_i][c_j]; } ++c_i; ++c_j; } if (s_i > 0) --s_i; else ++s_j; } // ---------------------- s_i = 1; s_j = m - 2; while (s_i < n && s_j >= 0) { c_i = s_i; c_j = s_j; while (c_i < n && c_j < m - 1) { char a = vec[c_i - 1][c_j]; char b = vec[c_i][c_j + 1]; if (a == b && b == vec[c_i][c_j]) { dp4[c_i][c_j] = min(dp4[c_i - 1][c_j], dp4[c_i][c_j + 1]) + 1; s += dp4[c_i][c_j]; } ++c_i; ++c_j; } if (s_j > 0) --s_j; else ++s_i; } cout << s << endl; return 0; }