XDOJ1327

题目描述

第七兽分为四个亚种，我们把它们记为 A, B, C, D。每只兽需要至少一个格子作为自己的领地。如果两只相邻的兽是一个亚种的，它们会融合成一只兽，这只兽将会占据以前两只兽的领地。 

珂朵莉想问威廉，在一个 n * m 的 铺满第七兽的四个亚种 的矩形里面，到底有多少只第七兽的四个亚种。

输入

第一行包括两个数 n, m, 表示这个矩形的大小。 

剩下行描述了这个矩形内兽的分布情况。

输出

输出一行四个数，表示第七兽 亚种 A, B, C, D 的个数，每两个数之间有一个空格。

样例输入

4 7DDDDDDDDABABADDBACACDDDDDDDD

样例输出

5 3 2 1

示例代码

#include 
    
     #include 
     
      #define N 55using namespace std;char data[N][N];void dfs(int x,int y,char s){	if(data[x][y]==s)	{		data[x][y] = 'E';		dfs(x+1,y,s);		dfs(x-1,y,s);		dfs(x,y+1,s);		dfs(x,y-1,s);	}}int main(){	int m,n;    cin >> m >> n;    int resu = 0;    memset(data,0,sizeof(data));    for(int i = 1 ; i <= m ;i++)    	for(int j = 1 ; j <=n ;j++)		cin >>data[i][j];    for(int i = 1 ; i <= m ;i++)    	for(int j = 1 ; j <=n ;j++)		if(data[i][j]=='A') dfs(i,j,'A'),resu++;		cout << resu << " ";	resu  = 0;	for(int i = 1 ; i <= m ;i++)    	for(int j = 1 ; j <=n ;j++)		if(data[i][j]=='B') dfs(i,j,'B'),resu++;		cout << resu << " ";	resu  = 0;	for(int i = 1 ; i <= m ;i++)    	for(int j = 1 ; j <=n ;j++)		if(data[i][j]=='C') dfs(i,j,'C'),resu++;		cout << resu << " ";	resu  = 0;	for(int i = 1 ; i <= m ;i++)    	for(int j = 1 ; j <=n ;j++)		if(data[i][j]=='D') dfs(i,j,'D'),resu++;		cout << resu ;		return 0;}
     
    

总结

笔者的代码通常长度上比较短，而且没有无用头文件，总体来说，这道题是一道比较常见的dfs，这道题据说用队列写也很简单，笔者有空尝试一下，稍后代码附上。

PS：这倒是暑训签到题，题号为B，笔者会尽力在8.1前完成其他题解。