#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool limites(int n, int m, int x, int y){
return x>=0&&x<n&&y>=0&&y<m;
}
ll count_rectangles(const vector<vector<int>>a) {
ll rect=0;
int n = a.size();
int m = a[0].size();
vector<vector<bool>>v(n,vector<bool>(m));
vector<int>dx={0,-1,0,1};
vector<int>dy={1,0,-1,0};
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
if(!v[i][j]&&a[i][j]==0){
v[i][j]=true;
queue<pair<int,int>>cola;
cola.push({i,j});
int l_x=n,r_x=0,l_y=m,r_y=0;
int cnt=0;
while(!cola.empty()){
pair<int,int>nodo=cola.front();
cola.pop();
l_x=min(l_x,nodo.first);
r_x=max(r_x,nodo.first);
l_y=min(l_y,nodo.second);
r_y=max(r_y,nodo.second);
cnt++;
for(int i=0;i<4;i++){
int x=nodo.first+dx[i],y=nodo.second+dy[i];
if(limites(n,m,x,y)){
if(a[x][y]==0){
if(!v[x][y]){
v[x][y]=true;
cola.push({x,y});
}
}
}
}
}
if(l_x==0)continue;
if(r_x==n-1)continue;
if(l_y==0)continue;
if(r_y==m-1)continue;
if(cnt==((r_x-l_x+1)*(r_y-l_y+1))){
rect++;
}
}
}
}
return rect;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
100 ms |
23132 KB |
Output is correct |
3 |
Correct |
233 ms |
62208 KB |
Output is correct |
4 |
Correct |
259 ms |
62492 KB |
Output is correct |
5 |
Correct |
240 ms |
62544 KB |
Output is correct |
6 |
Correct |
103 ms |
31140 KB |
Output is correct |
7 |
Correct |
202 ms |
58764 KB |
Output is correct |
8 |
Correct |
230 ms |
62584 KB |
Output is correct |
9 |
Correct |
0 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |