이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
ll count_rectangles(ve<ve<int>> A) {
int n, m;
ll ans;
ve<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
queue<pii> Q;
n = (int)A.size();
m = (int)A[0].size();
ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i][j] == 0) {
Q.push({i, j});
A[i][j] = -1;
int xMin = i;
int xMax = i;
int yMin = j;
int yMax = j;
int cnt = 1;
while (!Q.empty()) {
int x, y;
tie(x, y) = Q.front();
Q.pop();
for (int k = 0; k < 4; k++) {
int xNew = x + dx[k];
int yNew = y + dy[k];
if (0 <= xNew && xNew < n && 0 <= yNew && yNew < m) {
if (A[xNew][yNew] == 0) {
Q.push({xNew, yNew});
A[xNew][yNew] = -1;
xMin = min(xMin, xNew);
xMax = max(xMax, xNew);
yMin = min(yMin, yNew);
yMax = max(yMax, yNew);
cnt++;
}
}
}
}
if (xMin != 0 && xMax != n - 1 && yMin != 0 && yMax != m - 1) {
if ((xMax - xMin + 1) * (yMax - yMin + 1) == cnt) ans++;
}
}
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |