#include "rect.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 2510;
int n, m;
int g[MAXN][MAXN];
struct OWO {
int bruh, cnt, l, r, u, d;
bool check() {
if(bruh) return false;
int w = r - l + 1;
int h = d - u + 1;
return w * h == cnt;
}
void out() {
cout << "owo: ";
if(bruh) cout << "bruh\n";
else {
cout << cnt << " (";
cout << l << "-" << r << ", ";
cout << u << "-" << d << ")\n";
}
}
};
OWO merge(const OWO &a, const OWO &b) {
return (OWO){
a.bruh || b.bruh,
a.cnt + b.cnt,
min(a.l, b.l),
max(a.r, b.r),
min(a.u, b.u),
max(a.d, b.d)
};
}
// 0 for ok
// 1 for boundary
// 2 for outside
int check(int x, int y) {
if(x < 0 || x >= n || y < 0 || y >= m) return 2;
if(x == 0 || x == n - 1 || y == 0 || y == m - 1) return 1;
return 0;
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
OWO dfs(int sx, int sy) {
g[sx][sy] = 1;
OWO owo = (OWO){0, 0, sx, sx, sy, sy};
queue<pii> que;
que.emplace(sx, sy);
while(!que.empty()) {
int x, y;
tie(x, y) = que.front();
que.pop();
owo = merge(owo, (OWO){0, 1, x, x, y, y});
For(it, 0, 3) {
int nx = x + dx[it];
int ny = y + dy[it];
if(check(nx, ny) == 2) continue;
if(g[nx][ny] == 0) {
g[nx][ny] = 1;
que.emplace(nx, ny);
}
}
if(check(x, y) == 1) {
owo.bruh = 1;
}
}
return owo;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = sz(a);
m = sz(a[0]);
For(i, 0, n - 1) For(j, 0, m - 1) {
g[i][j] = a[i][j];
assert(g[i][j] < 2);
}
int res = 0;
For(i, 1, n - 2) For(j, 1, m - 2) if(g[i][j] == 0) {
auto owo = dfs(i, j);
res += owo.check();
// owo.out();
}
return res;
}
