#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2510;
int n, m;
int v[N][N];
// int linha[N][N][N], coluna[N][N][N];
int mark[N][N];
int lmax[N*N], lmin[N*N], rmax[N*N], rmin[N*N], qtd[N*N];
void dfs(int i, int j, int con){
mark[i][j] = con;
// cout << i << ' ' << j << ' ' << con << '\n';
qtd[con]++;
lmax[con] = max(lmax[con], i);
lmin[con] = min(lmin[con], i);
rmax[con] = max(rmax[con], j);
rmin[con] = min(rmin[con], j);
if(i > 1 and v[i-1][j] == 0 and mark[i-1][j] == 0) dfs(i-1, j, con);
if(i < n and v[i+1][j] == 0 and mark[i+1][j] == 0) dfs(i+1, j, con);
if(j > 1 and v[i][j-1] == 0 and mark[i][j-1] == 0) dfs(i, j-1, con);
if(j < m and v[i][j+1] == 0 and mark[i][j+1] == 0) dfs(i, j+1, con);
return;
}
int markcon[N*N];
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
v[i+1][j+1] = a[i][j];
}
}
int con = 1;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
if(mark[i][j] == 0 and v[i][j] == 0) {
lmax[con] = i; lmin[con] = i;
rmax[con] = j; rmin[con] = j;
dfs(i, j, con);
con++;
}
}
}
long long res = 0;
for(int i = 2;i < n;i++){
for(int j = 2;j < m;j++){
if(v[i][j] == 1) continue;
if(markcon[mark[i][j]] == 0){
markcon[mark[i][j]] = 1;
con = mark[i][j];
// cout << mark[i][j] << ' ';
// cout << lmax[con] << ' ' << lmin[con] << ' ' << rmax[con] << ' ' << rmin[con] << ' ' << qtd[con] << '\n';
if(qtd[con] == (lmax[con]-lmin[con]+1)*(rmax[con]-rmin[con]+1) and lmax[con] < n and lmin[con] > 1 and rmax[con] < m and rmin[con] > 1) res++;
}
}
}
return res;
// for(int l = 1;l <= n;l++){
// for(int i = 1;i <= m;i++){
// linha[l][i][i] = v[l][i];
// for(int j = i+1;j <= m;j++){
// linha[l][i][j] = max(linha[l][i][j-1], v[l][j]);
// }
// }
// }
// for(int c = 1;c <= m;c++){
// for(int i = 1;i <= n;i++){
// coluna[c][i][i] = v[i][c];
// for(int j = i+1;j <= m;j++){
// coluna[c][i][j] = max(coluna[c][i][j-1], v[j][c]);
// }
// }
// }
// int res = 0;
// for(int l1 = 2;l2 < n;l2++){
// for(int r1 = 2;r1 < n;r1++){
// }
// }
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
119 ms |
51536 KB |
Output is correct |
3 |
Correct |
226 ms |
119940 KB |
Output is correct |
4 |
Correct |
225 ms |
120600 KB |
Output is correct |
5 |
Correct |
226 ms |
120400 KB |
Output is correct |
6 |
Correct |
266 ms |
223796 KB |
Output is correct |
7 |
Correct |
597 ms |
538236 KB |
Output is correct |
8 |
Correct |
606 ms |
635860 KB |
Output is correct |
9 |
Correct |
1 ms |
2392 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |