Bailian4101 晶矿的个数【DFS】

4101:晶矿的个数
总时间限制: 1000ms 内存限制: 65536kB
描述
在某个区域发现了一些晶矿，已经探明这些晶矿总共有分为两类，为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域，若m[i][j]为#表示该地点是非晶矿地点，若m[i][j]为r表示该地点是红晶矿地点，若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图，求红晶矿和黑晶矿的个数。

输入
第一行为k，表示有k组测试输入。
每组第一行为n，表示该区域由n*n个地点组成，3 <= n<= 30
接下来n行，每行n个字符，表示该地点的类型。
输出
对每组测试数据输出一行，每行两个数字分别是红晶矿和黑晶矿的个数，一个空格隔开。
样例输入
2
6
r##bb#
###b##
#r##b#
#r##b#
#r####

4

#rrb
#rr#
##bb
样例输出
2 2
1 2

问题链接：Bailian4101 晶矿的个数
问题简述：（略）
问题分析：简单的DFS问题，分别计数一下就好了。为了保证连在一起的不要重复计算，用DFS来标记。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* Bailian4101 晶矿的个数 */

#include <bits/stdc++.h>

using namespace std;

const int N = 30;
char b[N][N + 1];
int n;

void dfs(int r, int c, char type)
{
    if(r < 0 || r >= n || c < 0 || c >= n) return;
    if(b[r][c] != type) return;
    b[r][c] = '#';
    dfs(r - 1, c, type);
    dfs(r + 1, c, type);
    dfs(r, c - 1, type);
    dfs(r, c + 1, type);
}

int main()
{
    int k;
    scanf("%d", &k);
    while(k--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%s", b[i]);

        int rcnt = 0, bcnt = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(b[i][j] == 'r') {
                    rcnt++;
                    dfs(i, j, 'r');
                } else if(b[i][j] == 'b') {
                    bcnt++;
                    dfs(i, j, 'b');
                }

        printf("%d %d\n", rcnt, bcnt);
    }

    return 0;
}