#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2503;
const int M = N * N;
const int di[] = {0, 0, 1, -1};
const int dj[] = {1, -1, 0, 0};
int n, m;
int ncc;
int vis[N][N];
int pref[N][N];
vector<vector<int>> a;
void Dfs (int x, int y) {
vis[x][y] = ncc;
for (int i = 0; i < 4; ++i) {
int nx = x + di[i];
int ny = y + dj[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (vis[nx][ny]) {
continue;
}
if (a[nx][ny] == 1) {
continue;
}
Dfs(nx, ny);
}
}
int mnX[M], mxX[M], mnY[M], mxY[M];
long long count_rectangles(std::vector<std::vector<int> > A) {
n = (int) A.size();
m = (int) A[0].size();
a = A;
for (int i = 1; i < n - 1; ++i) {
for (int j = 1; j < m - 1; ++j) {
if (!vis[i][j] && a[i][j] == 0) {
ncc++;
Dfs(i, j);
}
}
}
fill(mnX + 1, mnX + ncc + 1, N);
fill(mnY + 1, mnY + ncc + 1, N);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
mnX[vis[i][j]] = min(mnX[vis[i][j]], i);
mnY[vis[i][j]] = min(mnY[vis[i][j]], j);
mxX[vis[i][j]] = max(mxX[vis[i][j]], i);
mxY[vis[i][j]] = max(mxY[vis[i][j]], j);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
pref[i][j] = a[i][j];
if (i - 1 >= 0) {
pref[i][j] += pref[i - 1][j];
}
if (j - 1 >= 0) {
pref[i][j] += pref[i][j - 1];
}
if (i - 1 >= 0 && j - 1 >= 0) {
pref[i][j] -= pref[i - 1][j - 1];
}
}
}
auto qry = [&](int x, int y, int xx, int yy) {
return pref[xx][yy] - pref[xx][y - 1] - pref[x - 1][yy] + pref[x - 1][y - 1];
};
int ans = 0;
for (int i = 1; i <= ncc; ++i) {
if (mnX[i] > 0 && mxX[i] < n - 1 && mnY[i] > 0 && mxY[i] < m - 1) {
ans += qry(mnX[i], mnY[i], mxX[i], mxY[i]) == 0;
}
}
return ans;
}
