D - E搜索

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

Hint

题意：

我们拍了一张照片！ 照片是n*m个像素的！ 对于每个像素，都是一个小写英文字符。 如果连着走4步，是"girl"就是一个girl 如果连着走3步，是"cat"就是一只cat 然后问你，这个图上有多少个girl多少只cat

思路：

首先找到a,然后在对a上下左右进行寻找并分别记录下来c和t的个数，然后再找i上下左右，同上，然后在从r找l,并记录个数，那么cat或girl为c t或者g r l的乘积！！

代码：

#include<bits/stdc++.h> using namespace std; int m,n; inline bool ok(int x,int y) { if(x>=0&&x<m&&y>=0&&y<n) return 1; else return 0; } int main() { int t,i,j,k; string s[1000]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; cin>>t; while(t--) { cin>>m>>n; for(i=0;i<m;i++) cin>>s[i]; int cat=0,girl=0; for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(s[i][j]=='a') { int c=0,t=0; for(k=0;k<4;k++) { if(ok(i+dx[k],j+dy[k])&&s[i+dx[k]][j+dy[k]]=='c') c++; if(ok(i+dx[k],j+dy[k])&&s[i+dx[k]][j+dy[k]]=='t') t++; } cat+=c*t; } if(s[i][j]=='i') { int g=0,l=0; for(k=0;k<4;k++) { if(ok(i+dx[k],j+dy[k])&&s[i+dx[k]][j+dy[k]]=='g') g++; if(ok(i+dx[k],j+dy[k])&&s[i+dx[k]][j+dy[k]]=='r') { for(int kk=0;kk<4;kk++) { if(ok(i+dx[k]+dx[kk],j+dy[k]+dy[kk])&&s[i+dx[k]+dx[kk]][j+dy[k]+dy[kk]]=='l') { l++; } } } } girl+=g*l; } } } cout<<girl<<" "<<cat<<endl; } return 0; }

另外思路：

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<complex> #include<string> #include<algorithm> #include<iostream> #define exp 1e-10 using namespace std; const int N = 1005; const int M = 15; const int inf = 100000000; const int mod = 2009; char s[N][N],ch[2][5]={"girl","cat"}; bool v[N][N]; int ans[2],n,m; bool check(int x,int y) { return x>=0&&x<n&&y>=0&&y<m; } void dfs(int x,int y,int k,int t) { if(!check(x,y)||s[x][y]!=ch[t][k]) return; v[x][y]=true; if(t&&k==2||!t&&k==3) { ans[t]++; return; } dfs(x+1,y,k+1,t); dfs(x,y+1,k+1,t); dfs(x-1,y,k+1,t); dfs(x,y-1,k+1,t); } int main() { int t,i,j; scanf("%d",&t); while(t--) { ans[0]=ans[1]=0; memset(v,false,sizeof(v)); scanf("%d%d",&n,&m); for(i=0;i<n;i++) scanf("%s",s[i]); for(i=0;i<n;i++) for(j=0;j<m;j++) if(!v[i][j]) { if(s[i][j]=='g') dfs(i,j,0,0); else if(s[i][j]=='c') dfs(i,j,0,1); } printf("%d %d\n",ans[0],ans[1]); } return 0; }