#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long N,M,ufds[6500005],rnk[6500005],X1[6500005],X2[6500005],Y1[6500005],Y2[6500005], sz[6500005], dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
long long findSet(long long i) {
return ufds[i] == i ? i : ufds[i] = findSet(ufds[i]);
}
void unionSet(long long i, long long j) {
long long a = findSet(i), b = findSet(j);
if (a == b) return;
if (rnk[a] < rnk[b])
X1[b] = min(X1[a],X1[b]), X2[b] = max(X2[a],X2[b]), Y1[b] = min(Y1[a],Y1[b]), Y2[b] = max(Y2[a],Y2[b]), sz[b] += sz[a], ufds[a] = b;
if (rnk[a] > rnk[b])
X1[a] = min(X1[a],X1[b]), X2[a] = max(X2[a],X2[b]), Y1[a] = min(Y1[a],Y1[b]), Y2[a] = max(Y2[a],Y2[b]), sz[a] += sz[b], ufds[b] = a;
if (rnk[a] == rnk[b])
X1[b] = min(X1[a],X1[b]), X2[b] = max(X2[a],X2[b]), Y1[b] = min(Y1[a],Y1[b]), Y2[b] = max(Y2[a],Y2[b]), sz[b] += sz[a], ufds[a] = b, rnk[b]++;
}
long long count_rectangles(vector<vector<int> > a) {
N = a.size(), M = a[0].size();
for (long long i = 0; i < N; ++i) for (long long j = 0; j < M; ++j)
ufds[i*M+j] = i*M+j, rnk[i*M+j] = 1, X1[i*M+j] = X2[i*M+j] = i, Y1[i*M+j] = Y2[i*M+j] = j, sz[i*M+j] = 1;
for (long long i = 0; i < N; ++i) for (long long j = 0; j < M; ++j) if (a[i][j] == 0) {
for (long long k = 0; k < 4; ++k) {
long long nx = i + dx[k], ny = j + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < M && a[nx][ny] == 0) unionSet(i*M+j,nx*M+ny);
}
}
long long ans = 0;
for (long long i = 1; i < N-1; ++i) for (long long j = 1; j < M-1; ++j)
if (findSet(i*M+j) == i*M+j && a[i][j] == 0 && X1[i*M+j] != 0 && X2[i*M+j] != N-1 && Y1[i*M+j] != 0 && Y2[i*M+j] != M-1 && sz[i*M+j] == (X2[i*M+j]-X1[i*M+j]+1) * (Y2[i*M+j]-Y1[i*M+j]+1)) ans++;
return ans;
}
