#include "rect.h"
#include <queue>
#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair <int, int> pii;
#define TRACE(x) cerr << #x << ' ' << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define fi first
#define sec second
#define pb push_back
const int MAXN = 2501;
const int smjerx[] = {1, -1, 0, 0};
const int smjery[] = {0, 0, 1, -1};
int p[MAXN][MAXN];
int bio[MAXN][MAXN];
int n, m;
bool bfs(int X, int Y) {
queue <int> q;
q.push(X);
q.push(Y);
bio[X][Y] = 1;
int maxX = X;
int maxY = Y;
int minX = X;
int minY = Y;
int rub = 0;
int cnt = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
int y = q.front();
q.pop();
maxX = max(maxX, x);
maxY = max(maxY, y);
minX = min(minX, x);
minY = min(minY, y);
cnt++;
if (x == 0 || x == n - 1 || y == 0 || y == m - 1) rub++;
REP(i, 4) {
int nx = x + smjerx[i];
int ny = y + smjery[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || bio[nx][ny] || p[nx][ny]) continue;
bio[nx][ny] = 1;
q.push(nx);
q.push(ny);
}
}
return (rub == 0) && (maxX - minX + 1) * (maxY - minY + 1) == cnt;
}
long long solve1() {
int ret = 0;
REP(i, n) REP(j, m) {
if (bio[i][j] || p[i][j]) continue;
ret += bfs(i, j);
}
return ret;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
REP(i, n) REP(j, m) p[i][j] = a[i][j];
int maks = 0;
REP(i, n) REP(j, m) maks = max(maks, p[i][j]);
if (maks == 1) return solve1();
return 1;
}
