#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
const int mxn = 2510;
int par[mxn * mxn], cnt[mxn * mxn], n, m;
pair<pair<int, int>, pair<int, int>> dp[mxn * mxn];
bool is[mxn][mxn];
void mnn(int &a, int b) {
if(a > b) a = b;
}
void mxx(int &a, int b) {
if(a < b) a = b;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int toInt(pair<int, int> a) {
return (a.ff - 1) * n + a.ss;
}
int get(int x) {
if(par[x] == x) return x;
return par[x] = get(par[x]);
}
void unite(int x, int y) {
x = get(x), y = get(y);
if(x == y) return;
if(cnt[x] < cnt[y]) swap(x, y);
par[y] = x;
cnt[x] += cnt[y];
mxx(dp[x].ss.ff, dp[y].ss.ff);
mxx(dp[x].ss.ss, dp[y].ss.ss);
mnn(dp[x].ff.ff, dp[y].ff.ff);
mnn(dp[x].ff.ss, dp[y].ff.ss);
}
long long count_rectangles(vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i][j] == 0) {
dp[i * n + j] = {{i, j}, {i, j}};
par[i * n + j] = i * n + j;
cnt[i * n + j] = 1;
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i][j]) continue;
for(int k = 0; k < 4; k++) {
int ii = i + dx[k], jj = j + dy[k];
if(ii >= 0 && ii < n && jj >= 0 && jj < m && A[ii][jj] == 0) {
unite(i * n + j, ii * n + jj);
}
}
}
}
long long ret = 0;
set<int> s;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i][j] == 1) continue;
int id = get(i * n + j);
if(s.find(id) != s.end()) continue;
s.in(id);
if((dp[id].ss.ff - dp[id].ff.ff + 1) * (dp[id].ss.ss - dp[id].ff.ss + 1) == cnt[id] &&
dp[id].ff.ff > 0 && dp[id].ff.ss > 0 && dp[id].ss.ff < n - 1 && dp[id].ss.ss < m - 1) ret++;
}
}
return ret;
}
