简答题
偏难
#7193
晶矿的个数 在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描…
晶矿的个数
在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域,若m[i][j]为#表示该地点是非晶矿地点,若m[i][j]为r表示该地点是红晶矿地点,若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图,求红晶矿和黑晶矿的个数。
时间限制:1000
内存限制:65536
输入
第一行为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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。