踏青 计蒜客习题 (dfs)

题头:

蒜头君和他的朋友周末相约去召唤师峡谷踏青。他们发现召唤师峡谷的地图是由一块一块格子组成的，有的格子上是草丛，有的是空地。草丛通过上下左右 4 个方向扩展其他草丛形成一片草地，任何一片草地中的格子都是草丛，并且所有格子之间都能通过上下左右连通。如果用'#'代表草丛，'.'代表空地，下面的峡谷中有 2 片草地。

1 ##..

2 ..##

处在同一个草地的 2 个人可以相互看到，空地看不到草地里面的人。他们发现有一个朋友不见了，现在需要分头去找，每个人负责一片草地，蒜头君想知道他们至少需要多少人。

输入格式
第一行输入 n, m (1≤n,m≤100) 表示峡谷大小

接下来输入 n 行字符串表示峡谷的地形

输入格式
输出至少需要多少人

样例输入

5 6
.#....
..#...
..#..#
...##.
.#....
样例输出

5

#include 
using namespace std;
char p[101][101];
int n, m;
int visit[101][101] = {0};
int head[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};//表示方向的数组
void dfs(int x, int y)
{
    int tx, ty;
    for (int i = 0; i < 4; i++)
    {
        tx = x + head[i][0];//四方向搜索
        ty = y + head[i][1];
       if (tx >= 0 && ty >= 0 && p[tx][ty] == '#' && visit[tx][ty] == 0)
            {
                visit[tx][ty] = 1;
                p[tx][ty] = '.';
                dfs(tx, ty);
            }
    }
}//深度优先搜索
int main()
{

    int i, j;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
        {
            cin >> p[i][j];
        }
    int ans = 0;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
        {
            if (p[i][j] == '#' && visit[i][j] != 1)
            {
                ans++;
                dfs(i,j);
            }
        }
        cout<<ans;
}
//思路:对每个地块进行搜索,用一个visit数组记录是否来过,如果找到草地,就将visit值置为1,并变为普通地面
//搜索时从第一个草地开始排查(因为找到一块后,这块草地会清空,所以不会影响后面的查找),ans++

(dfs类)第一次做这种类型,吸取了别人的经验