#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
int n, m;
vector<vector<int>> field;
vector<vector<vector<pii>>> dp;
pii bound(int x, int y, int type) {
if (field[x][y] == 1) return {0, 0};
if (x == 0 || x == n-1 || y == 0 || y == m-1) return {-1, -1};
if (dp[x][y][type].fi != -2) {
return dp[x][y][type];
}
vector<tuple<int, int, int>> nexts;
if (type == 0) {
if (field[x][y-1] == 0) return {-1, -1};
if (field[x-1][y] == 0) return {-1, -1};
nexts.push_back({x+1, y, 1});
nexts.push_back({x, y+1, 2});
}
else if (type == 1) {
if (field[x][y-1] == 0) return {-1, -1};
nexts.push_back({x+1, y, 1});
nexts.push_back({x, y+1, 3});
}
else if (type == 2) {
if (field[x-1][y] == 0) return {-1, -1};
nexts.push_back({x+1, y, 3});
nexts.push_back({x, y+1, 2});
}
else{
nexts.push_back({x+1, y, 3});
nexts.push_back({x, y+1, 3});
}
vector<pii> res;
for (auto &i : nexts) {
res.push_back(bound(get<0>(i), get<1>(i), get<2>(i)));
}
pii re = {res[0].fi+1, res[1].se+1};
if (res[0].fi == -1 || res[1].fi == -1) re = {-1, -1};
if (res[0].fi != 0 && res[1].fi != 0 && res[0].fi+1 != res[1].fi) re = {-1, -1};
if (res[0].se != 0 && res[1].se != 0 && res[1].se+1 != res[0].se) re = {-1, -1};
dp[x][y][type] = re;
return re;
}
ll count_rectangles(vector<vector<int> > a) {
field = a;
n = a.size(); m = a[0].size();
ll cmax = 0;
dp.assign(n, vector<vector<pii>>(m, vector<pii>(4, {-2, -2})));
for (int i1 = 1; i1 < n-1; i1++)
{
for (int j1 = 1; j1 < m-1; j1++)
{
if (bound(i1, j1, 0).fi != -1) {
cmax++;
}
}
}
return cmax;
}
