#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, m;
bool valid(int x, int y) {
if (x >= 0 && x<n && y >= 0 && y < m) return true;
else return false;
}
ll count_rectangles(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
vector<vector<bool>> vis(n, vector<bool>(m, false));
/*vector<vector<int>> rows(n, vector<int>(m, 0));
for (int i=0; i<n; i++) {
rows[i][0] = a[i][0];
for (int j=1; j<m; j++) {
rows[i][j] = rows[i][j-1] + a[i][j];
}
}
vector<vector<int>> col(m, vector<int>(n, 0));
for (int i=0; i<m; i++) {
col[i][0] = a[0][i];
for (int j=1; j<n; j++) {
col[i][j] = a[j][i] + col[i][j-1];
}
}*/
ll ans=0;
for (int i=1; i<n-1; i++) {
for (int j=1; j<m-1; j++) {
if (!vis[i][j] && a[i][j] == 0) {
vis[i][j] = true;
int mnx = i;
int mxx = i;
int mny = j;
int mxy = j;
queue<pii> q;
q.push({i, j});
int cnt=0;
while (!q.empty()) {
int ni = q.front().first;
int nj = q.front().second;
cnt++;
q.pop();
for (int k=0; k<4; k++) {
int x = ni+dx[k];
int y = nj+dy[k];
if (valid(x, y) && a[x][y] == 0 && !vis[x][y]) {
vis[x][y] = true;
mxx = max(mxx, x);
mnx = min(mnx, x);
mny = min(mny, y);
mxy = max(mxy, y);
q.push({x, y});
}
}
}
if ((mxx-mnx+1) * (mxy-mny+1) == cnt && mny != 0 && mnx != 0 && mxx != n-1 && mxy != m-1) {
ans++;
}
}
}
}
return ans;
}
