[백준] 1184 귀농

모든 꼭짓점 (x,y)에 대해, 이 점을 공유하는 넓이가 같은 사각형의 수를 세는 문제다. 쉽게 푼 사람들은 쉽게 푼거같은데.. 난 더럽게 푼거같다

처음에 map만 써야되는데 아무 의미없는 set도 같이 써서 시간초과가 났다

문제는 꼭짓점 x,y를 정하고 그 점을 중심으로 양쪽 대각선 방향으로 넓이를 비교해주면 된다!

1) 왼쪽 위, 오른쪽 아래

2) 오른쪽 위, 왼쪽 아래

이렇게 두번 보면 된다

위에있는 값들을 map에 넣고 수를 센다

그리고 아래있는 값들이 map에 들어 있다면 답에 더해준다!

넓이를 구하는건 펜윅트리를 사용했다..! 그냥 배열로도 구할 수 있지만 갑자기 쓰고싶어서..!

소스코드

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
int tree[111][111];
int n,ans;
map<int, int> mp;
int _sum(int x, int y) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i&-i)) {
        for (int j = y; j > 0; j -= (j&-j)) {
            ret += tree[i][j];
        }
    }
    return ret;
}
int sum(int a, int b, int x, int y) {
    return _sum(x, y) - _sum(a - 1, y) - _sum(x, b - 1) + _sum(a - 1, b - 1);
}
void update(int x, int y, int val) {
    for (int i = x; i <= n; i += (i&-i)) {
        for (int j = y; j <= n; j += (j&-j)) {
            tree[i][j] += val;
        }
    }
}
 
void f(int x,int y) {
    mp.clear();
    for (int i = x; i >= 1; i--) {
        for (int j = y; j >= 1; j--) {
            int rect = sum(i, j, x, y);
            if (mp.count(rect)) mp[rect]++;
            else mp[rect] = 1;
        }
    }
    for (int i = x + 1; i <= n; i++) {
        for (int j = y + 1; j <= n; j++) {
            int rect = sum(x + 1, y + 1, i, j);
            if (mp.count(rect)) ans += mp[rect];
        }
    }
}
 
void g(int x,int y) {
    mp.clear();
    for (int i = x; i >= 1; i--) {
        for (int j = y; j <= n; j++) {
            int rect = sum(i, y, x, j);
            if (mp.count(rect)) mp[rect]++;
            else mp[rect] = 1;
        }
    }
    for (int i = x + 1; i <= n; i++) {
        for (int j = y - 1; j >= 1; j--) {
            int rect = sum(x + 1, j, i, y - 1);
            if (mp.count(rect)) ans += mp[rect];
        }
    }
}
int main() {
    scanf(" %d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x; scanf(" %d", &x);
            update(i, j, x);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f(i, j); g(i, j);
        }
    }
    printf("%d\n", ans);
}