GirlCat
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
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×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.
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×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 Twhich represents the case number.
As for each case, the first line are
two integers n and m , which are the height and the width of the photo.
Then there are n lines followed, and there are m characters of each line, which are the the details of the photo.
It is
guaranteed that:
T is about 50.
1≤n≤1000 .
1≤m≤1000 .
∑(n×m)≤2×10^6.
As for each case, the first line are
two integers n and m , which are the height and the width of the photo.
Then there are n lines followed, and there are m characters of each line, which are the the details of the photo.
It is
guaranteed that:
T is about 50.
1≤n≤1000 .
1≤m≤1000 .
∑(n×m)≤2×10^6.
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.
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
Source
题解：一张n*m的英文字母照片，要求找到cat和gril，字母组成只需要连续，可以转弯。
思路：先找到首字母g和c的下标，用DFS找到gril和cat。因为能够走到的地方要是上一个格子的字母的下一个字母，所以这里极大的限制了Dfs走的层数，也极大的限制了能够走到的地方的个数，所以是不会超时的。
代码：
#include<stdio.h>
#include<string.h>
using namespace std;
char a[][];
int fx[]={,,-,};
int fy[]={,-,,}; //平移坐标
int ans;
int n,m;
void Dfs(int x,int y)
{
for(int i=;i<;i++)
{
int xx=x+fx[i]; //上下左右四个点搜索
int yy=y+fy[i];
if(xx>=&&xx<n&&yy>=&&yy<m)
{
if(a[x][y]=='g'&&a[xx][yy]=='i'||a[x][y]=='i'&&a[xx][yy]=='r')
{
Dfs(xx,yy); //上一个是g，找到了i就继续搜索，上一个是i，找到了r就继续搜索
}
if(a[x][y]=='r'&&a[xx][yy]=='l')ans++; 如果找到了r且下一个是l，答案+
}
}
}
void Dfs2(int x,int y)
{
for(int i=;i<;i++)
{
int xx=x+fx[i];
int yy=y+fy[i];
if(xx>=&&x<n&&yy>=&&yy<m)
{
if(a[x][y]=='c'&&a[xx][yy]=='a')
{
Dfs2(xx,yy);
}
if(a[x][y]=='a'&&a[xx][yy]=='t')
{
ans++;
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
scanf("%s",a[i]);
}
int output=;
int output2=;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
if(a[i][j]=='g') //标记g的坐标，开始深搜girl
{
ans=;
Dfs(i,j);
output+=ans;
}
if(a[i][j]=='c') //标记c，深搜cat
{
ans=;
Dfs2(i,j);
output2+=ans;
}
}
}
printf("%d %d\n",output,output2);
}
}
第二发