[蓝桥杯2023年第十四届省赛真题-岛屿个数] Floodfill算法

解题思路: 可以在地图的最外边加一圈外海‘0’，从外海开始深搜，如果遇到‘1’就搜索岛屿并且标记，因为如果是环岛只会搜到最外圈，否则海水会蔓延到岛里面，还要注意的是海水是八连通方向，而岛屿是四连通方向。

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 60;

int g[N][N];

int t, n, m, cnt;

int dx1[] = {0, 0, 1, -1}, dy1[] = {1, -1, 0, 0};

int dx2[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy2[] = {-1, 0, 1, 1, 1, 0, -1, -1};

bool st[N][N];

void dfs_1(int x, int y)

{

    st[x][y] = true;

    for (int i = 0; i < 4; i++)

    {

        int tx = dx1[i] + x, ty = dy1[i] + y;

        if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && !st[tx][ty] && g[tx][ty])

            dfs_1(tx, ty);

    }

}

void dfs_2(int x, int y)

{

    st[x][y] = true;

    for (int i = 0; i < 8; i++)

    {

        int tx = x + dx2[i], ty = y + dy2[i];

        if (tx >= 0 && tx <= n + 1 && ty >= 0 && ty <= m + 1 && !st[tx][ty])

            if (!g[tx][ty]) dfs_2(tx, ty);

            else dfs_1(tx, ty), cnt++;

    }

}

int main()

{

    scanf("%d", &t);

    while (t--)

    {

        cnt = 0;

        memset(g, 0, sizeof g);

        memset(st, false, sizeof st);

        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; i++) 

            for (int j = 1; j <= m; j++)

            {

                char x;

                cin >> x;

                g[i][j] = x - '0';

            }

        dfs_2(0, 0);

        printf("%d\n", cnt);

    }

    return 0;

}