TZOJ 2799：数羊 深搜

描述

前段时间我失眠了。我曾经躺着醒着，盯着天花板，好几个小时。有一天，我的祖母建议我在睡觉后试着数羊。像往常一样，当我的祖母提出建议时，我决定尝试一下。唯一的问题是，当我上床睡觉时，周围没有羊可以数。

输入

输入的第一行包含一个数字 T，即要遵循的测试用例的数量。

每个测试用例都以包含两个数字 H 和 W 的行开始，即羊网格的高度和宽度。然后是 H 行，每行包含 W 个字符（# 或 .），描述网格的该部分。

输出

对于每个测试用例，输出一行包含单个数字，即根据问题描述中所述的规则网格表示的羊群数量。

注释和约束
0 < T <= 100
0 < H,W <= 100

样例输入

2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###

样例输出

6
3

#include
using namespace std;
int n,m,ans,sum,f,maxx;
char a[101][101];//地图 
bool book[101][101];//标记数组 
int nex[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//方向 
void dfs(int x,int y)
{
    int tx,ty;
    for(int i=0;i<4;i++)
    {
        tx = nex[i][0]+x;
        ty = nex[i][1]+y;
        if(tx<1||tx>n||ty<1||ty>m)continue;//是否越界 
        if(a[tx][ty]=='#'&&book[tx][ty]==0)//判断下一步是否可走 
        {
            book[tx][ty]=1;//标记已走 
            dfs(tx,ty);//继续搜 
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(book,0,sizeof(book));//情况标记数组 
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
            getchar();//吃掉回车 
        }
        ans = 0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(a[i][j]=='#'&&book[i][j]==0)//如果是#号并且没有标记过 
                {
                    book[i][j]=1;//标记走过 
                    ans++;//羊群+1 
                    dfs(i,j);
                }
            }
        }
        cout<endl;
    }
    
    return 0;
}