[C/C++] BOJ #1012 organic cabbages

There are cabbages planted in your vegetable garden, and you want to grow them organically by releasing cabbage whiteworms. A single cabbage whiteworm is sufficient to prevent pests, as it can move to adjacent cabbages in the cluster.

This problem is similar to the “number of islands” problem and other common problems. It can be solved using the basic DFS or BFS algorithms in graph theory.

 

You can use either BFS or DFS, as both can traverse all adjacent areas. Personally, I prefer DFS because it is much simpler to implement.

 

0	0	0	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0
0	0	1	0	0	0	1	1	1	0
0	0	1	0	0	0	0	1	1	0
0	1	1	0	0	0	0	0	0	0
0	0	0	1	1	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0

 

Whether you use DFS or BFS, it doesn’t matter which node you start with. If the data is stored in an array, you can sequentially search through the array and use a DFS algorithm starting from any cell where the array value is 1. During the DFS process, you replace the value of 1 with a non-1 value.  By doing so, in the main() function, every time you find a 1 in the array, you can count a new worm.

 

organic cabbages

Below is the code I wrote. Please use it for reference only.

//----------------------------------------------------------
//    baekjoon #1012 - Organic Cabbages
//        - by Aubrey Choi
//        - created at 2019-08-01
//----------------------------------------------------------
#include <stdio.h>
#include <memory.h>

void dfs(char v[], int y, int x, int n, int m)
{
    int d[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
    v[y*m+x] = 0;
    for(int i = 0; i < 4; i++)
    {
        int nx = x+d[i][1], ny = y+d[i][0];
        if(nx<0||nx>=m||ny<0||ny>=n||v[ny*m+nx]==0) continue;
        dfs(v, ny, nx, n, m);
    }
}

int main()
{
    int t, m, n, k, x, y;
    char v[2500];
    scanf("%d", &t);
    while(t--)
    {
        int ans = 0;
        scanf("%d%d%d", &m, &n, &k);
        memset(v, 0, m*n);
        while(k--)
        {
            scanf("%d%d", &x, &y);
            v[y*m+x] = 1;
        }
        for(int i = 0; i < m*n; i++)
        {
            if(!v[i]) continue;
            dfs(v, i/m, i%m, n, m);
            ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}