題干：

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

解題報告：

因為單詞都很短，所以直接對于每一個起點bfs，長度超過5的時候就不再繼續(xù)bfs了，這樣保證復(fù)雜度是近似O(n*m)的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; char s[1005][1005]; int nx[4] = {0,1,0,-1}; int ny[4] = {1,0,-1,0}; char nn[555]; int n,m; struct Node {int x,y,t;char ch;Node(){}Node(int x,int y,int t,char ch):x(x),y(y),t(t),ch(ch){} }; int bfs(int stx,int sty,char st,char tar) {int res = 0;queue<Node> q;q.push(Node(stx,sty,0,st));while(!q.empty()) {Node cur = q.front();q.pop();if(cur.ch == tar) {res++;continue;}if(cur.t > 5) continue;for(int k = 0; k<4; k++) {int tx = cur.x + nx[k];int ty = cur.y + ny[k];if(tx<1||tx>n||ty<1||ty>m) continue;if(s[tx][ty] == nn[cur.ch]) q.push(Node(tx,ty,cur.t+1,s[tx][ty]));}}return res; } int main() {nn['g']='i';nn['i']='r';nn['r']='l';nn['c']='a';nn['a']='t';int t;cin>>t;while(t--) {ll ans1 = 0,ans2 = 0;scanf("%d%d",&n,&m);for(int i = 1; i<=n; i++) scanf("%s",s[i]+1);for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {if(s[i][j] == 'g') ans1 +=bfs(i,j,'g','l');}}for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {if(s[i][j] == 'c') ans2 +=bfs(i,j,'c','t');}}printf("%lld %lld\n",ans1,ans2);} return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 5706】GirlCat（bfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。