#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2503
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int a[MAXN][MAXN];
int p[MAXN][MAXN];
int r[MAXN][MAXN];
int c[MAXN][MAXN];
int get(int i, int j, int I, int J){
return p[I][J] - p[i - 1][J] - p[I][j - 1] + p[i - 1][j - 1];
}
bool check(int i, int j, int I, int J){
int ans = get(i - 1, j - 1, I + 1, J + 1);
ans -= a[I + 1][J + 1] + a[i - 1][J + 1] + a[I + 1][j - 1] + a[i - 1][j - 1];
return (ans == (2 * (I + J - i - j + 2)));
}
ll count_rectangles(vector<vector<int>> rec){
int n, m, I, J;
ll ans = 0;
n = rec.size();
m = rec[0].size();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] = rec[i - 1][j - 1];
p[i][j] = a[i][j] + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
}
}
for(int i = n; i > 0; i--){
for(int j = m; j > 0; j--){
if(a[i][j] == 0){
r[i][j] = max(i, r[i + 1][j]);
c[i][j] = max(j, c[i][j + 1]);
}
}
}
for(int i = 2; i < n; i++){
for(int j = 2; j < m; j++){
if(a[i][j] > 0) continue;
I = r[i][j], J = c[i][j];
if(I < n && J < m && get(i, j, I, J) == 0 && check(i, j, I, J))
ans++;
}
}
return ans;
}
