解题思路:

将问题看做从一个岛屿(x, y)点向外扩散红色水

大陆上是4通路扩散，到海里就是8通路扩散

为啥大陆上要4通路？因为如下两座岛，是不相连的，但是在大陆上8通路就会认为相连：

100
010
000

如果当前红色水扩散到地图边界了（要出地图了），就表示当前(x, y)出来的岛屿不是子岛屿，答案就加一

扩散的时候，标记岛屿不再访问了，但是海水访问过的要复原，以便下次访问

详细看代码注释

参考代码:

#include using namespace std;

int m, n;
vector d;
bool v[51][51];
bool flag;
int d1[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int d2[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

/**
 * 将问题看做从一个岛屿(x, y)点向外扩散红色水
 * 大陆上是4通路扩散，到海里就是8通路扩散
 * 为啥大陆上要4通路，因为如下两座岛，是不相连的，但是在大陆上8通路就会认为相连：
 *  100
 *  010
 *  000
 * 如果当前红色水扩散到地图边界了（要出地图了），就表示当前(x, y)出来的岛屿不是子岛屿，答案就加一
 * 扩散的时候，标记岛屿不再访问了，但是海水访问过的要复原，以便下次访问
 */
void flooding(int x, int y, int bak) {
    // printf("%d %d %d\n", x, y, bak);
    // 如果扩散到边界了，说明当前岛屿没有被其他岛屿包住，不是子岛屿
    if (x < 0 || x >= m || y < 0 || y >= n) {flag = true; return;}
    int nb = d[x][y] == '0' ? 0 : 1; // 当前地块的种类，存整数
    if (bak == 0 && nb == 1) return; // 如果从0到1，就表示从海水碰到其他岛屿边界了，停止扩散了
    if (v[x][y]) return; // 如果已经访问过了，那么就不继续扩散了
    v[x][y] = true;
    if (nb == 1) { // 如果当前是岛屿，这时已经默认从1扩散到1的，就继续向4通路扩散
        for (auto [a, b] : d1) flooding(x + a, y + b, nb);
    }
    if (nb == 0) { // 如果当前是海水，这时不论是从0/1扩散到0的，就继续向8通路扩散
        for (auto [a, b] : d2) flooding(x + a, y + b, nb);
    }
}

// 复原海水的访问状态
void flush_zero() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (v[i][j] && d[i][j] == '0') v[i][j] = false;
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> m >> n;
        d.clear();
        memset(v, false, sizeof(v));
        for (int i = 0; i < m; i++) {
            string s;
            cin >> s;
            d.push_back(s);
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][j] == '0' || v[i][j]) continue;
                flag = false;
                flooding(i, j, 1);
                if (flag) ans++;
                flush_zero();
            }
        }
        cout << ans << endl;
    }
    return 0;
}