"巴卡斯杯" 中国大学生程序设计竞赛 - 女生专场 E - GirlCat

小鱼儿 2022-04-17 01:51 207阅读 0赞

> As a cute girl, Kotori likes playing \`\`Hide and Seek'' with cats particularly.   
> Under the influence of Kotori, many girls and cats are playing \`\`Hide and Seek'' together.   
> Koroti shots a photo. The size of this photo is n×mn×m, each pixel of the photo is a character of the lowercase(from \`a' to \`z').   
> Kotori wants to know how many girls and how many cats are there in the photo.   
>   
> We define a girl as -- we choose a point as the start, passing by 4 different connected points continuously, and the four characters are exactly \`\`girl'' in the order.   
> We define two girls are different if there is at least a point of the two girls are different.   
> We define a cat as -- we choose a point as the start, passing by 3 different connected points continuously, and the three characters are exactly \`\`cat'' in the order.   
> We define two cats are different if there is at least a point of the two cats are different.   
>   
> Two points are regarded to be connected if and only if they share a common edge. 
> 
> Input
> 
> The first line is an integer TT which represents the case number.   
>   
> As for each case, the first line are two integers nn and mm, which are the height and the width of the photo.   
> Then there are nn lines followed, and there are mm characters of each line, which are the the details of the photo.   
>   
> It is guaranteed that:   
> TT is about 50.   
> 1≤n≤10001≤n≤1000.   
> 1≤m≤10001≤m≤1000.   
> ∑(n×m)≤2×106∑(n×m)≤2×106. 
> 
> Output
> 
> As for each case, you need to output a single line.   
> There should be 2 integers in the line with a blank between them representing the number of girls and cats respectively.   
>   
> Please make sure that there is no extra blank.   
>  
> 
> Sample Input
> 
>     3
>     1 4
>     girl
>     2 3
>     oto
>     cat
>     3 4
>     girl
>     hrlt
>     hlca
> 
> Sample Output
> 
>     1 0
>     0 2
>     4 1

#include<iostream>
    #include<queue>
    #include<algorithm>
    #include<map>
    #include<cstring>
    #include<string>
    using namespace std;
    
    int n,m;
    string s[1000+10];
    bool vis[1005][1005];
    map<char,char>mp;
    int dx[5] ={1,-1,0,0} ;
    int dy[5] ={0,0,1,-1};
    
    struct node
    {
    	char ch;
    	int x,y;
    };
    
    int ans_girl,ans_cat;
    
    void bfs(int r,int c,char ch)
    {
    	queue<node>q;
    	
    	node zero;
    	zero.x  =r; zero.y  =c;zero.ch = ch;
    	q.push(zero);
    	
    	while (!q.empty())
    	{
    		node front = q.front();
    		q.pop();
    		vis[front.x][front.y] = true;
    		if (front.ch=='l')
    		{
    			ans_girl++;
    			continue;
    		}
    		if (front.ch=='t')
    		{
    			ans_cat++;
    			continue;
    		}
    		for (int i=0;i<4;i++)
    		{
    			int x = dx[i]+front.x;
    			int y = dy[i]+front.y;
    			if (x<0||x>=n||y<0||y>=m) 
    			continue;
    			if (s[x][y]!=mp[front.ch]) 
    			continue;
    			
    			node temp;
    			temp.x = x;temp.y = y;temp.ch = s[x][y];
    			q.push(temp);
    			
    		}
    	}
    	
    	
    }
    
    int main()
    {
    	int T;
    	cin>>T;
    	mp['g'] = 'i';
    	mp['i'] = 'r';
    	mp['r'] = 'l';
    	mp['c'] = 'a';
    	mp['a'] = 't';
    	while (T--)
    	{
    		memset(vis,false,sizeof(vis));
    		ans_girl = 0;
    		ans_cat = 0;
    		cin>>n>>m;
    		for (int i=0;i<n;i++)
    		cin>>s[i];
    		
    		for (int i=0;i<n;i++)
    		{
    			for (int j=0;j<m;j++)
    			{
    				if (!vis[i][j]&&s[i][j]=='g'||s[i][j]=='c')
    				bfs(i,j,s[i][j]);
    			}
    		}
    		cout<<ans_girl<<" "<<ans_cat<<endl;
    	}
    	
    	
    	return 0;
    }