1012번: 유기농 배추

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


$O(tmn)$

flood fill을 이용하여 지렁이 수를 구한다.

#include<stdio.h>
const int MAX_N = 50, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int ck[MAX_N][MAX_N], t, m, n, k;
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= m || y >= n || !ck[x][y]) return;
    ck[x][y] = 0;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", &m, &n, &k);
        for (int i = 0, x, y; i < k; i++) scanf("%d %d", &x, &y), ck[x][y] = 1;
        int r = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) if (ck[i][j]) r++, dfs(i, j);
        printf("%d\n", r);
    }
    return 0;
}