链接：https://ac.nowcoder.com/acm/contest/558/J
来源：牛客网

小猫在研究网格图。
小猫在研究联通性。
给定一张N×M的网格图，只含字符0和1，问1形成的联通块有多少个。
两个1是联通的，当且仅当其中一个位于另一个的上、下、左、右四个方向之一。

思路：dfs水题，判断联通块的数量

#include <bits/stdc++.h>
using namespace std;
char str[1005];
int mp[100][100];
int vis[105][105];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int cnt;
void dfs(int x, int y) {
    cnt++;
    vis[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (!vis[nx][ny] && mp[nx][ny]) {
            dfs(nx, ny);
        }
    }
}
 
int main() {
    int T;
    scanf("%d", &T);
    int n, m;
    int a, b, c;
    while (T--) {
        memset(vis, 0, sizeof(vis));
        memset(mp, 0, sizeof(mp));
        scanf("%d%d", &n, &m);
        for (int i =1 ; i <= n; i++) {
            scanf("%s", str + 1);
            for (int j = 1; j <= m; j++) {
                mp[i][j] = str[j] - '0';
            }
        }
         
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!vis[i][j] && mp[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}