#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
typedef long long ll;
const int MAXN = 2500;
ll sum(ll x) {
return x * (x+1) / 2;
}
ll count_rectangles(vector<vector<int>> mat) {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n = sz(mat);
int m = sz(mat[0]);
ll ans = 0;
for (int i1=1; i1<n-1; i1++) {
for (int j1=1; j1<m-1; j1++) {
// if (i1 == 3 and j1 == 8) cerr << mat[i1-1][j1] << ' ' << mat[i1][j1-1] << ' ' << mat[i1][j1] << '\n';
if (mat[i1-1][j1] != 1 or mat[i1][j1-1] != 1 or mat[i1][j1] != 0) continue;
// cerr << i1 << ' ' << j1 << '\n';
// cerr << mat[i1][j1]
int i2=i1, j2=j1;
bool can = true;
for (int j=j1+1; j<m; j++) {
if (mat[i1][j] == 1) break;
j2++;
if (mat[i1-1][j] == 0) {
can = false;
break;
}
}
if (j2 == m-1 or !can) continue;
for (int i=i1+1; i<n; i++) {
if (mat[i][j1] == 1) {
for (int j=j1; j<=j2; j++) {
if (mat[i][j] == 0) {
can = false;
break;
}
}
break;
}
if (mat[i][j1-1] == 0 or mat[i][j2+1] == 0) {
can = false;
break;
}
for (int j=j1; j<=j2; j++) {
if (mat[i][j] == 1) {
can = false;
break;
}
}
if (!can) break;
i2++;
}
if (i2 == n-1 or !can) continue;
// cerr << i1 << ' ' << j1 << '\n';
// cerr << "conseguiu: " << j2-j1+1 << " x " << i2-i1+1 << '\n';
// ans += sum(j2-j1+1) * sum(i2-i1+1);
ans++;
}
}
return ans;
}
