| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 396523 | blue | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
using namespace std;
/*
For each (i, j)
T[i][j] = furthest row I such that T[I][j], T[I+1][j], ... T[i-1][j] all have height less than (i, j)
Similarly, D[i][j], R[i][j], L[i][j]
A rectangle (r1, r2, c1, c2) is good if(minD[r1-1][c1..c2] > r2) and so on
*/
vector< vector<int> > A;
int cc = 0;
vector<int> t, l, d, r;
vector<int> s;
int n, m;
void dfs(int i, int j)
{
if(A[i][j]) continue;
A[i][j] = 1;
t[cc-1] = min(t[cc-1], i);
d[cc-1] = max(d[cc-1], i);
l[cc-1] = min(l[cc-1], j);
r[cc-1] = max(r[cc-1], j);
s[cc-1]++;
if(i > 0) dfs(i-1, j);
if(i < n-1) dfs(i+1, j);
if(j > 0) dfs(i, j-1);
if(j < m-1) dfs(i, j+1);
}
long long count_rectangles(vector< vector<int> > a)
{
A = a;
n = A.size();
m = A[0].size();
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(A[i][j]) continue;
cc++;
s.push_back(0);
t.push_back(1e9);
l.push_back(1e9);
d.push_back(-1);
r.push_back(-1);
dfs(i, j);
}
long long res = 0;
for(int i = 0; i < cc; i++)
{
if(t[i] == 0 || l[i] == 0 || d[i] == n-1 || r[i] == m-1) continue;
if(s[i] == (d[i]-t[i]+1) * (r[i]-l[i]+1))
res++;
}
return res;
}