#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2505;
int dx[4] = {-1, 1, 0, 0},
dy[4] = {0, 0, -1, 1};
bool used[N][N];
int mn_x, mx_x, mn_y, mx_y, ct, n, m;
void dfs(vector<vector<int>> &a, int x, int y) {
used[x][y] = 1;
ct++;
mn_x = min(mn_x, x);
mx_x = max(mx_x, x);
mn_y = min(mn_y, y);
mx_y = max(mx_y, y);
for (int i = 0; i < 4; i++) {
int p = x + dx[i],
q = y + dy[i];
if (p >= 0 && p < n && q >= 0 && q < m &&
a[p][q] == 0 && !used[p][q]) {
dfs(a, p, q);
}
}
}
bool check(vector<vector<int>> &a, int xl, int xr, int yl, int yr) {
for (int i = xl; i <= xr; i++) {
for (int j = yl; j <= yr; j++) {
if (a[i][j] >= a[i][yl - 1] ||
a[i][j] >= a[i][yr + 1] ||
a[i][j] >= a[xl - 1][j] ||
a[i][j] >= a[xr + 1][j]) {
return false;
}
}
}
return true;
}
ll solve_slow(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
ll ans = 0;
for (int xl = 1; xl < n - 1; xl++) {
for (int yl = 1; yl < m - 1; yl++) {
for (int xr = xl; xr < n - 1; xr++) {
for (int yr = yl; yr < m - 1; yr++) {
if (check(a, xl, xr, yl, yr))
ans++;
}
}
}
}
return ans;
}
ll solve01(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!used[i][j] && a[i][j] == 0) {
mn_x = N, mx_x = -1, mn_y = N, mx_y = -1, ct = 0;
dfs(a, i, j);
if (mn_x > 0 && mx_x < n - 1 &&
mn_y > 0 && mx_y < m - 1 &&
ct == (mx_x - mn_x + 1) * (mx_y - mn_y + 1)) {
ans++;
}
}
}
}
return ans;
}
ll count_rectangles(vector<vector<int>> a) {
return solve01(a);
}
