#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2510;
int a[maxn][maxn];
int desno[maxn][maxn];
int dolje[maxn][maxn];
int pref[maxn][maxn];
int suma(int x1, int y1, int x2, int y2){
return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
}
long long count_rectangles(vector<vector<int> > b) {
int n = b.size();
int m = b[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
a[i + 1][j + 1] = b[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
pref[i][j] = pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + a[i][j];
}
}
// cout << suma(1, 1, 3, 3) << ' ' << suma(2, 2, 2, 2) << endl;
for(int i = 1; i <= n; i++){
desno[i][m + 1] = m + 1;
for(int j = m; j >= 1; j--){
desno[i][j] = desno[i][j + 1];
if(a[i][j]) desno[i][j] = j;
}
}
for(int j = 1; j <= m; j++){
dolje[n + 1][j] = n + 1;
for(int i = n; i >= 1; i--){
dolje[i][j] = dolje[i + 1][j];
if(a[i][j]) dolje[i][j] = i;
}
}
int ans = 0;
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
if(!a[i][j] || a[i + 1][j + 1]) continue;
int r = desno[i + 1][j + 1];
int d = dolje[i + 1][j + 1];
if(d == i + 1 || r == j + 1) continue;
if(d == n + 1 || r == m + 1) continue;
if(suma(i, j, d, r) == 2 * (d - i) + 2 * (r - j) && suma(i + 1, j + 1, d - 1, r - 1) == 0){
ans++;
// cout << i << ' ' << j << ' ' << d << ' ' << r << ' ' << pref[6][6] << ' ' << pref[3][6] << ' ' << pref[6][3] << ' ' << pref[3][3] << endl;
}
}
}
return ans;
}
