#include using namespace std; using ll=long long; using ld=long double; using vi=vector; using ii=pair; #define FOR(i,a,b) for(int i=a; i < b; i++) #define F(n) FOR(i, 0, n) #define FF(n) FOR(j, 0, n) #define aa first #define bb second #define PB push_back int main() { ios::sync_with_stdio(0); int N, M; cin >> N >> M; vector> T(N, vector(M)); for (auto && row : T) for (auto && v : row) cin >> v; vector> L(N, vector(M)); vector> R(N, vector(M)); vector> U(N, vector(M)); vector> D(N, vector(M)); for (int i = 0; i < N; i++) for (int j = M - 2; j >= 0; j--) R[i][j] = ((T[i][j] == T[i][j+1]) ? R[i][j+1] + 1 : 0); for (int i = 0; i < N; i++) for (int j = 1; j < M; j++) L[i][j] = ((T[i][j] == T[i][j-1]) ? L[i][j-1] + 1 : 0); for (int i = 1; i < N; i++) for (int j = 0; j < M; j++) U[i][j] = ((T[i][j] == T[i-1][j]) ? U[i-1][j] + 1 : 0); for (int i = N - 2; i >= 0; i--) for (int j = 0; j < M; j++) D[i][j] = ((T[i][j] == T[i+1][j]) ? D[i+1][j] + 1 : 0); vector> RD(N, vector(M)); vector> RU(N, vector(M)); vector> LD(N, vector(M)); vector> LU(N, vector(M)); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { RU[i][j] = min(R[i][j], U[i][j]); RD[i][j] = min(R[i][j], D[i][j]); LU[i][j] = min(L[i][j], U[i][j]); LD[i][j] = min(L[i][j], D[i][j]); } vector> TRD(N, vector(M)); vector> TRU(N, vector(M)); vector> TLD(N, vector(M)); vector> TLU(N, vector(M)); int i, j; vector> starts; for (int j = 0; j < M; j++) starts.emplace_back(N - 1, j); for (int i = 0; i < N; i++) starts.emplace_back(i, M - 1); starts.pop_back(); for (auto && s : starts) { tie(i, j) = s; i--; j--; for (; i >= 0 && j >= 0; i--, j--) { if (T[i][j] == T[i+1][j+1]) TRD[i][j] = min(RD[i][j], TRD[i+1][j+1]+2); else TRD[i][j] = (RD[i][j] != 0); } } starts.clear(); for (int j = 0; j < M; j++) starts.emplace_back(0, j); starts.pop_back(); for (int i = 0; i < N; i++) starts.emplace_back(i, M - 1); for (auto && s : starts) { tie(i, j) = s; i++; j--; for (; i < N && j >= 0; i++, j--) { if (T[i][j] == T[i-1][j+1]) TRU[i][j] = min(RU[i][j], TRU[i-1][j+1]+2); else TRU[i][j] = (RU[i][j] != 0); } } starts.clear(); for (int j = 0; j < M; j++) starts.emplace_back(N - 1, j); for (int i = 0; i < N; i++) starts.emplace_back(i, 0); starts.pop_back(); for (auto && s : starts) { tie(i, j) = s; i--; j++; for (;i >= 0 && j < M; i--, j++) { if (T[i][j] == T[i+1][j-1]) TLD[i][j] = min(LD[i][j], TLD[i+1][j-1]+2); else TLD[i][j] = (LD[i][j] != 0); } } starts.clear(); for (int j = 0; j < M; j++) starts.emplace_back(0, j); for (int i = 1; i < N; i++) starts.emplace_back(i, 0); for (auto && s : starts) { tie(i, j) = s; i++; j++; for (; i < N && j < M; i++, j++) { if (T[i][j] == T[i-1][j-1]) TLU[i][j] = min(LU[i][j], TLU[i-1][j-1]+2); else TLU[i][j] = (LU[i][j] != 0); } } /* for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { cout << "TRD: " << i << ' ' << j << '\n'; cout << TRD[i][j] << '\n'; cout << "TRU: " << i << ' ' << j << '\n'; cout << TRU[i][j] << '\n'; cout << "TLD: " << i << ' ' << j << '\n'; cout << TLD[i][j] << '\n'; cout << "TLU: " << i << ' ' << j << '\n'; cout << TLU[i][j] << '\n'; } */ int sum = 0; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) sum += TRD[i][j] + TRU[i][j] + TLD[i][j] + TLU[i][j]; cout << sum << '\n'; return 0; }