No testdata at current.

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

连通块可以认为是互相可以到达的一些点。

搜索还常用来解决连通块个数，最大连通块等等问题。

***.
.*.*
**.*

比如这个图，如果'*'是草地，'.'是空地，如果认为有公共边的格子是相互连通的（即一个格子和它周围上、下、左、右四个格子连通），那么图中草地一共有 2 个连通块，一个大小为 6 ，一个大小为 2 。

求连通块个数可以依次从每一个有效的没被访问过的点出发，往四周搜索直到出界或者遇到空地，一共出发了多少次就是有多少连通块，每一次可以统计这一次走了多少个格子，也就是这个连通块的大小。

写成代码来看是这样

void dfs(int x, int y) {
    cnt++; // 这个连通块的大小
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] == '*') {
            dfs(tx, ty);
        }
    }
}

然后调用的时候是这样

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (maze[i][j] == '*' && !vis[i][j]) {
            ans++; // 连通块数量
            cnt = 0; // 这个连通块的大小
            dfs(i, j);
            mx = max(mx, cnt); // 求最大连通块
        }
    }
}

只认为上、下、左、右四个方向是连通的情况常被称作四连通，如果把左上、右上、左下、右下这四个方向也看作连通就常被称作八连通。