#include <bits/stdc++.h>
#include "rect.h"
using ll = long long;
using namespace std;
const int MAXN = 2510;
int mat[MAXN][MAXN];
int marc[MAXN][MAXN];
int n, m;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
bool check(int x, int y){
return 1 < x && x < n && 1 < y && y < m && mat[x][y] == 0;
}
ll min_x, min_y, max_x, max_y, cur = 0;
vector<pair<ll, ll>> comp;
void dfs(ll x, ll y){
marc[x][y] = cur;
comp.push_back({x, y});
min_x = min(min_x, x);
min_y = min(min_y, y);
max_x = max(max_x, x);
max_y = max(max_y, y);
for(int k=0; k<4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(!marc[nx][ny] && check(nx, ny)) dfs(nx, ny);
}
}
ll count_rectangles(vector<vector<int>> a){
n = (int) a.size();
m = (int) a[0].size();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
mat[i + 1][j + 1] = a[i][j];
}
}
dfs(1, 1);
ll ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(marc[i][j] || mat[i][j] == 1) continue;
min_x = min_y = 1e9;
max_x = max_y = 0;
cur ++;
comp.clear();
dfs(i, j);
if((max_x - min_x + 1) * (max_y - min_y + 1) == (int) comp.size()){
// eh um retangulo
// checo se todas as bordas sao 1
bool ok = true;
for(auto [x, y] : comp){
for(int k=0; k<4; k++){
int nx = x + dx[k], ny = y + dy[k];
if(marc[nx][ny] == cur || mat[nx][ny] == 1) continue;
ok = false;
}
}
if(ok) ans ++;
}
}
}
return ans;
}
