#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "rect.h"
namespace my {
const int N = 2520;
const int INF = N;
int n, m;
int a[N][N];
bool used[N][N];
int cnt = 0;
int li, lj, ri, rj;
bool bad;
void dfs(int i, int j) {
if ((i == 0 || j == 0 || i == n - 1 || j == m - 1) && !a[i][j]) {
bad = true;
return;
}
if (used[i][j] || a[i][j] || i < 1 || i > n - 2 || j < 1 || j > m - 2) {
return;
}
used[i][j] = true;
li = min(li, i); ri = max(ri, i);
lj = min(lj, j); rj = max(rj, j);
++cnt;
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
}
}
ll count_rectangles(vector<vector<int>> _a) {
using namespace my;
n = (int)_a.size(), m = (int)_a[0].size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
a[i][j] = _a[i][j];
}
}
int answer = 0;
for (int i = 1; i < n - 1; ++i) {
for (int j = 1; j < m - 1; ++j) {
if (used[i][j] || a[i][j]) {
continue;
}
cnt = 0;
bad = false;
li = INF, lj = INF, ri = -INF, rj = -INF;
dfs(i, j);
if (!bad && cnt == (ri - li + 1) * (rj - lj + 1)) {
++answer;
}
}
}
return answer;
}
#ifdef LC
#include "grader.cpp"
#endif
