#include <bits/stdc++.h>
using namespace std;
void print_vvint(vector<vector<int>>& grid) {
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
}
int max_col(vector<vector<int>>& grid, int x, int y1, int y2) {
int m = INT32_MIN;
for (int y = y1; y <= y2; y++) {
m = max(m, grid[y][x]);
}
return m;
}
int max_row(vector<vector<int>>& grid, int y, int x1, int x2) {
int m = INT32_MIN;
for (int x = x1; x <= x2; x++) {
m = max(m, grid[y][x]);
}
return m;
}
bool is_valid(vector<vector<int>>& grid, int x1, int y1, int x2, int y2) {
int m = INT32_MIN;
for (int y = y1; y <= y2; y++) {
for (int x = x1; x <= x2; x++) {
m = max(m, grid[y][x]);
}
}
// top + bottom
for (int x = x1; x <= x2; x++) {
int maxCol = max_col(grid, x, y1, y2);
if (maxCol >= grid[y1-1][x] || maxCol >= grid[y2+1][x]) return false;
}
// left + right
for (int y = y1; y <= y2; y++) {
int maxRow = max_row(grid, y, x1, x2);
if (maxRow >= grid[y][x1-1] || maxRow >= grid[y][x2+1]) return false;
}
return true;
}
int64_t count_rectangles(std::vector<std::vector<int> > a) {
int accumulator = 0;
for (int y1 = 1; y1 < a.size()-1; y1++) {
for (int x1 = 1; x1 < a[y1].size()-1; x1++) {
for (int y2 = y1; y2 < a.size()-1; y2++) {
for (int x2 = x1; x2 < a[y2].size()-1; x2++) {
// cout << "checking (" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ")" << endl;
// cout << is_valid(a, x1, y1, x2, y2) << endl;
if (is_valid(a, x1, y1, x2, y2)) {
// cout << "valid (" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ")" << endl;
accumulator++;
}
}
}
}
}
return accumulator;
}
