A41760. 晶矿的个数在某个区域发现了一些晶矿，已经探明这些晶矿总共有分为两类，为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域，若m[i][j]为#表示该地点是非晶矿地点，若m[i][j]为r表示该地点是红晶矿地点，若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图，求红晶矿和黑晶矿的个数。…
填空题
困难
知识点
题目描述
晶矿的个数
在某个区域发现了一些晶矿，已经探明这些晶矿总共有分为两类，为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图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
参考答案
//示例代码
#include <bits/stdc++.h>
using namespace std;
char map_[35][35];
int x[4]={-1,1,0,0};
int y[4]={0,0,-1,1};
struct x_y{
int a,b;
x_y(int x,int y){a=x;b=y;}
};
int k,n,red,black;
void bfs(int a,int b,char c){
queue<x_y> q;
x_y t(a,b);
q.push(t);
map_[a][b]='#';
while(!q.empty()){
t=q.front();
q.pop();
for(int i=0;i<4;i++){
int aa=t.a+x[i];
int bb=t.b+y[i];
if(aa>=1&&aa<=n&&bb>=1&&bb<=n&&map_[aa][bb]==c){
x_y tt(aa,bb);
q.push(tt);
map_[aa][bb]='#';
}
}
}
}
int main()
{
cin>>k;
while(k--){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>map_[i][j];
}
red=black=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(map_[i][j]=='r'){
bfs(i,j,'r');
red++;
}
else if(map_[i][j]=='b'){
bfs(i,j,'b');
black++;
}
}
cout<<red<<" "<<black<<endl;
}
return 0;
}
上一题
下一题