HDU5706 GirlCat(简单dfs)

超、凢脫俗 2022-08-22 13:28 5阅读 0赞

# **HDU5706 GirlCat (简单dfs)** #

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.

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 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**

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

--------------------

链接在这：[题目链接][Link 1]

寻找里面有多少girl和cat  
简单的dfs

**代码：**

#include<stdio.h>
    #include<string.h>
    using namespace std;
    
    char girl[4]= {
       'g','i','r','l'};
    char cat[3]= {
       'c','a','t'};
    int dxy[4][2]={
       0,1,0,-1,1,0,-1,0};
    char map[1005][1005];
    int vis[1005][1005];
    int m,n;
    int ans1,ans2;
    
    void dfs1(int x,int y,int s)
    {
        if(x<0||x>=n||y<0||y>=m||vis[x][y]==1||s>3||s<0)
            return;
        if(s==3)
        {
            if(map[x][y]==girl[3])
            {
                ans1++;
            }
            return;
        }
        else if(map[x][y]!=girl[s])
            return;
        else if(map[x][y]==girl[s])
        {
            vis[x][y]=1;
            int nx,ny;
            for(int i=0;i<4;i++)
            {
                nx=x+dxy[i][0];
                ny=y+dxy[i][1];
                dfs1(nx,ny,s+1);
            }
            vis[x][y]=0;
        }
    }
    
    void dfs2(int x,int y,int s)
    {
        if(x<0||x>=n||y<0||y>=m||vis[x][y]==1||s>2||s<0)
            return;
        if(s==2)
        {
            if(map[x][y]==cat[2])
            {
                ans2++;
            }
            return;
        }
        else if(map[x][y]!=cat[s])
            return;
        else if(map[x][y]==cat[s])
        {
            vis[x][y]=1;
            int nx,ny;
            for(int i=0;i<4;i++)
            {
                nx=x+dxy[i][0];
                ny=y+dxy[i][1];
                dfs2(nx,ny,s+1);
            }
            vis[x][y]=0;
        }
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            ans1=0,ans2=0;
            memset(vis,0,sizeof(vis));
            scanf("%d %d",&n,&m);
            getchar();
            for(int i=0; i<n; i++)
            {
                for(int j=0;j<m;j++)
                {
                    scanf("%c",&map[i][j]);
                }
                getchar();
            }
            if(n*m<3)
            {
                printf("0 0\n");
                continue;
            }
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<m; j++)
                {
                    if(map[i][j]=='g');
                    {
                        dfs1(i,j,0);
                    }
                    if(map[i][j]=='c');
                    {
                        dfs2(i,j,0);
                    }
                }
            }
            printf("%d %d\n",ans1,ans2);
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5706