#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int R = 3e3 + 5, C = 3e3 + 5, INF = 1e18;
int r, c;
arr<arr<int, C>, R> a;
arr<arr<int, C>, R> rw;
arr<arr<int, R>, C> cl;
void rw_cl_cmp() {
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
rw[i][j] = rw[i][j - 1] + (!a[i][j]);
for (int j = 1; j <= c; j++)
for (int i = 1; i <= r; i++)
cl[j][i] = cl[j][i - 1] + (!a[i][j]);
}
vec<pii> adj(int i, int j) {
vec<pii> opt = {{i - 1, j}, {i + 1, j}, {i, j - 1}, {i, j + 1}}, ans;
for (pii x : opt)
if (1 <= x.fir && x.fir <= r && 1 <= x.sec && x.sec <= c)
ans.push_back(x);
return ans;
}
arr<arr<bool, C>, R> vs;
vec<pii> cmp;
void dfs(int i, int j) {
vs[i][j] = true, cmp.push_back({i, j});
for (pii x : adj(i, j))
if (!vs[x.fir][x.sec] && !a[x.fir][x.sec]) dfs(x.fir, x.sec);
}
bool chck() {
int w = INF, x = -1, y = INF, z = -1;
for (pii xx : cmp) {
w = min(w, xx.fir);
x = max(x, xx.fir);
y = min(y, xx.sec);
z = max(z, xx.sec);
}
if (cmp.size() != (x - w + 1) * (z - y + 1)) return false;
if (w == 1 || x == r || y == 1 || z == c) return false;
if (rw[w - 1][z] - rw[w - 1][y - 1]) return false;
if (rw[x + 1][z] - rw[x + 1][y - 1]) return false;
if (cl[y - 1][x] - cl[y - 1][w - 1]) return false;
if (cl[z + 1][x] - cl[z + 1][w - 1]) return false;
return true;
}
int ans_cmp() {
int ans = 0;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (vs[i][j]) continue;
if (a[i][j]) continue;
cmp.clear();
dfs(i, j);
// for (pii x : cmp) {
// cout << x.fir << "," << x.sec << " ";
// }
// cout << endl;
ans += chck();
}
}
return ans;
}
int count_rectangles(vec<vec<sig>> _a) {
r = _a.size(), c = _a[0].size();
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
a[i][j] = _a[i - 1][j - 1];
rw_cl_cmp();
int ans = ans_cmp();
return ans;
}
