/*
Uses UFDS
Note: valid exactly when it satisfies:
(1) area condition
(2) no border condition (i.e., the max/min x and y of the component is within the bounds)
*/
#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
struct UF {
int c, n;
vi par, csize, minx, maxx, miny, maxy;
UF(int y, int x): c(x), n(x * y), par(x * y, 0), csize(x * y, 1), minx(x * y, 2500), maxx(x * y, 0), miny(x * y, 2500), maxy(x * y, 0) {
for(int i = 0; i < n; i++) {
par[i] = i;
}
for(int j = 0; j < y; j++) {
for(int i = 0; i < x; i++) {
int cid = coord(j, i);
minx[cid] = i;
maxx[cid] = i;
miny[cid] = j;
maxy[cid] = j;
}
}
};
int coord(int y, int x) {
return y * c + x;
}
int find(int y, int x) {
int c_coord = coord(y, x);
return find(c_coord);
}
int find(int i) {
return (i == par[i] ? i : par[i] = find(par[i]));
}
bool conn(int y1, int x1, int y2, int x2) {
return find(y1, x1) == find(y2, x2);
}
void unify(int y1, int x1, int y2, int x2) {
int pari = find(y1, x1), parj = find(y2, x2);
if(pari == parj) return;
int new_minx = min(minx[pari], minx[parj]);
int new_maxx = max(maxx[pari], maxx[parj]);
int new_miny = min(miny[pari], miny[parj]);
int new_maxy = max(maxy[pari], maxy[parj]);
int new_csize = csize[pari] + csize[parj];
if(csize[pari] < csize[parj]) {
// i into j
par[pari] = parj;
csize[parj] = new_csize;
minx[parj] = new_minx;
maxx[parj] = new_maxx;
miny[parj] = new_miny;
maxy[parj] = new_maxy;
} else {
par[parj] = pari;
csize[pari] = new_csize;
minx[pari] = new_minx;
maxx[pari] = new_maxx;
miny[pari] = new_miny;
maxy[pari] = new_maxy;
}
}
};
ll count_rectangles(vvi a) {
int rows = a.size(), cols = a[0].size();
UF uf(rows, cols);
for(int y = 0; y < rows; y++) {
for(int x = 0; x < cols; x++) {
if(a[y][x] == 1) continue;
if(x < cols - 1 && a[y][x + 1] == 0) uf.unify(y, x, y, x + 1);
if(y < rows - 1 && a[y + 1][x] == 0) uf.unify(y, x, y + 1, x);
}
}
set<int> good_comps;
for(int y = 1; y < rows - 1; y++) {
for(int x = 1; x < cols - 1; x++) {
int cid = uf.find(y, x);
if(a[y][x] == 1) continue;
if(uf.minx[cid] == 0 || uf.maxx[cid] == cols - 1 || uf.miny[cid] == 0 || uf.maxy[cid] == rows - 1) continue;
if(good_comps.count(cid) > 0) continue;
if((uf.maxx[cid] - uf.minx[cid] + 1) * (uf.maxy[cid] - uf.miny[cid] + 1) == uf.csize[cid]) good_comps.insert(cid);
}
}
return good_comps.size();
}
