#include "rect.h"
#include <bits/stdc++.h>
#define uwu return
using namespace std;
const int MAX_N = 2.5e3 + 5;
bitset <MAX_N> graph[MAX_N];
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int NN, MM;
vector <int> dfs(int x, int y){
graph[x][y] = 1;
vector<int> ret = {x, x, y, y, 1};
for (int d = 0; d < 4; d++){
if(x + dx[d] < 0 || y + dy[d] < 0 || x + dx[d] > NN + 1 || y + dy[d] > MM + 1 || graph[x + dx[d]][y + dy[d]])
continue;
vector<int> tmp = dfs(x + dx[d], y + dy[d]);
ret[0] = min(ret[0], tmp[0]);
ret[2] = min(ret[2], tmp[2]);
ret[1] = max(ret[1], tmp[1]);
ret[3] = max(ret[3], tmp[3]);
ret[4] += tmp[4];
}
return ret;
}
long long count_rectangles(vector<vector<int> > a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
graph[i + 1][j + 1] = (a[i][j] == 1);
}
}
int ret = 0;
NN = n;
MM = m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if(graph[i][j])
continue;
vector<int> tmp = dfs(i, j);
ret += (tmp[1] - tmp[0] + 1) * (tmp[3] - tmp[2] + 1) == tmp[4];
}
}
uwu ret;
}
