#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2512;
int n, m;
long long sp[MAXN][MAXN];
int dir[MAXN][MAXN], bax[MAXN][MAXN];
long long area(int i, int j, int k, int l) {
return sp[k][l] - sp[k][j - 1] - sp[i - 1][l] + sp[i - 1][j - 1];
}
int tb[MAXN][MAXN];
long long count_rectangles(vector<vector<int> > ts) {
n = ts.size();
m = ts[0].size();
if(n < 3 || m < 3) return 0;
long long resp = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
tb[i + 1][j + 1] = ts[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sp[i][j] = tb[i][j] + sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];
}
}
for(int i = n; i >= 1; i--) {
for(int j = m; j >= 1; j--) {
if(tb[i][j] == 0) {
if(i == n) bax[i][j] = n + 1;
else bax[i][j] = bax[i + 1][j];
if(j == m) dir[i][j] = m + 1;
else dir[i][j] = m + 1;
}
else {
bax[i][j] = i;
dir[i][j] = j;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int lar = dir[i][j] - j, alt = bax[i][j] - i;
if(lar == 0 || dir == 0) continue;
int ptx = i + alt, pty = j + lar;
if(area(i, j, ptx, pty) != 0) continue;
if(area(i - 1, j, i - 1, pty) != lar) continue;
if(area(ptx + 1, j, ptx + 1, pty) != lar) continue;
if(area(i, j - 1, ptx, j - 1) != alt) continue;
if(area(i, pty + 1, ptx, pty + 1) != alt) continue;
resp++;
}
}
return resp;
}
