#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2500 + 5;
bool vis[MAX_N][MAX_N];
int R_max, R_min, C_max, C_min;
const int dr[] = {+1, -1, +0, +0};
const int dc[] = {+0, +0, +1, -1};
vector<vector<int>> mat;
int R, C;
int dfs(int r, int c) {
if (r <= 0 || c <= 0 || r >= R - 1 || c >= C - 1) {
return -2 * MAX_N * MAX_N;
}
R_min = min(R_min, r);
R_max = max(R_max, r);
C_min = min(C_min, c);
C_max = max(C_max, c);
vis[r][c] = 1;
int res = 1;
for (int i = 0; i < 4; i++) {
if (vis[r + dr[i]][c + dc[i]]) continue;
if (mat[r + dr[i]][c + dc[i]] > mat[r][c]) continue;
vis[r + dr[i]][c + dc[i]] = 1;
res += dfs(r + dr[i], c + dc[i]);
}
return res;
}
long long count_rectangles(vector<vector<int> > mat) {
::mat = mat;
R = mat.size();
C = mat[0].size();
if (R <= 2) {
return 0;
}
if (C <= 2) {
return 0;
}
// Subtask #6
long long res = 0;
for (int i = 1; i < R - 1; i++) {
for (int j = 1; j < C - 1; j++) {
if (!vis[i][j] && mat[i][j] == 0) {
R_max = C_max = -1;
R_min = C_min = 1e9;
int cur = dfs(i, j);
int expected = (R_max - R_min + 1) * (C_max - C_min + 1);
res += (cur == expected);
}
}
}
return res;
}
