Hdoj 5706 GirlCat

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 playingHide 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' toz’).
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 exactlycat” 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 T which 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×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

Source
“巴卡斯杯” 中国大学生程序设计竞赛 - 女生专场

题目分析
很水的DFS，详见代码
Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cctype> 
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=1010;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,-1,0,1};
const char girl[5]="girl";
const char cat[4]="cat";
char maze[maxn][maxn];
int n,m;
bool isFine(int x,int y)
{
    if( x<1 || x>n || y<1 || y>m) return false;
    return true;
}
int dfs_girl(int x,int y,int len)
{
    if(!isFine(x,y)) return 0;
    if(maze[x][y]!=girl[len]) return 0;
    if(3==len) return 1;
    int sum=0;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        sum+=dfs_girl(xx,yy,len+1);
    }
    return sum;
}
int dfs_cat(int x,int y,int len)
{
    if(!isFine(x,y)) return 0;
    if(maze[x][y]!=cat[len]) return 0;
    if(2==len) return 1;
    int sum=0;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        sum+=dfs_cat(xx,yy,len+1);
    }
    return sum;
}
int main() 
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>maze[i][j];
        int ans_girl=0,ans_cat=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                switch(maze[i][j])
                {
                    case 'g':ans_girl+=dfs_girl(i,j,0); break;
                    case 'c':ans_cat+=dfs_cat(i,j,0); break;
                }
            }
        cout<<ans_girl<<" "<<ans_cat<<endl;
    }
    return 0;
}

更多问题请关注个人博客，不定时更新