고인물이싫어 (백준 30508)

안녕하세요. 오늘은 고인물이 싫을거예요.

문제

https://www.acmicpc.net/problem/30508

아이디어

1. 웅덩이에서 올라가는 BFS/DFS를 통해 물을 빼낸다.
2. 남은 칸들중 물이 있으면 1, 없으면 0을 저장한다.
3. 누적합을 사용해서 h*w의 공간에서의 합이 0이면 물이 없는 것이므로 cnt++한다.

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int map[1010][1010] = { 0 }, N, M;
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
void BFS(int x, int y)
{
    if (map[x][y] == 0) return;
    queue <pair <pair <int,int>, int> > q;
    int curx, cury, num, nx, ny, i;

    q.push({ { x,y } ,map[x][y]}); map[x][y] = 0;
    while (q.size())
    {
        curx = q.front().first.first;
        cury = q.front().first.second;
        num = q.front().second;
        q.pop();

        for (i = 0; i < 4; i++)
        {
            nx = curx + dx[i]; ny = cury + dy[i];
            
            if (nx<1 || nx>N || ny<1 || ny>M) continue;
            if (map[nx][ny] < num) continue;
            q.push({ {nx,ny},map[nx][ny] }); map[nx][ny] = 0;
        }
    }
}

int sum[1010][1010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int h, w, i, j, K, x, y;

    cin >> N >> M >> h >> w;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            cin >> map[i][j];
    cin >> K;
    for (i = 0; i < K; i++)
    {
        cin >> x >> y;
        BFS(x, y);
    }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (bool)(map[i][j]);

    int cnt = 0;
    for (i = 1; i <= N - h + 1; i++)
        for (j = 1; j <= M - w + 1; j++)
            if (sum[i + h - 1][j + w - 1] - sum[i + h - 1][j - 1] - sum[i - 1][j + w - 1] + sum[i - 1][j - 1] == 0)
                cnt++;
    cout << cnt;
}

감사합니다.