本题要求求一个地图中的岛屿数量，但是不包括子岛屿（在其它岛屿围成的环之间）。

对于求岛屿，可以使用搜索中的 Flood Fill 算法来实现，对每个为 11 的陆地进行 BFS，标记与它相邻的所有陆地。为了实现环内部的岛屿不被统计，我们可以先 BFS 海域，在 BFS 海域的过程中如果遍历到为 11 的陆地，就来一遍 Flood Fill 将其相邻的陆地全部打上标记，如果遍历到为 00 的海水就不入队（只有 00 会入队）。

需要注意的是，遍历海域是八个方向拓展的，而遍历陆地是四个方向扩展的。同时我们能保证海水拓展八个方向得到的岛屿都不在环内，这是因为陆地不入队，岛屿在环内的话是进不去的。可以借助下面样例来理解：

1
2
3
4
5
01111
11001
10101
10001
11111

我们不可能遍历到 (3,2)(3,2) 位置的 00 的，因为 00 不入队，遍历海域是进不到环内的，自然就遍历不到环内的 11 了。所以我们对于每次 Flood Fill，直接将答案加 11 就可以了。

还有一些需要注意的点：

  • 我们需要确定遍历海水的起点。起点肯定要在最外面，所以我们默认图的下标从 11 开始，将 g0,ig_{0,i}、gi,0g_{i,0}、gn+1,ig_{n+1,i} 和 gi,m+1g_{i,m+1} 均设为 00，我们只需要从 (0,0)(0,0) 位置开始遍历就可以了。
  • 本题为多测，需要在每个测试数据都初始化一遍 visvis 数组和存图的 gg 数组（否则无法保证每次 g0,ig_{0,i}、gi,0g_{i,0}、gn+1,ig_{n+1,i} 和 gi,m+1g_{i,m+1} 均为 00）。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
typedef pair<int,int> PII;

int n,m,ans;
char g[N][N];
bool vis[N][N];

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

void bfs1(int x,int y)
{
    ans++;
    queue<PII> q;
    q.push({x,y});
    vis[x][y] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int x = t.first,y = t.second;
        for(int i=0;i<4;i++)
        {
            int rx = x+dx1[i],ry = y+dy1[i];
            if(rx>=1 && rx<=n && ry>=1 && ry<=m && !vis[rx][ry] && g[rx][ry] == '1')
            {
                vis[rx][ry] = true;
                q.push({rx,ry});
            }
        }
    }
}

void bfs2()
{
    queue<PII> q;
    q.push({0,0});
    vis[0][0] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int x = t.first,y = t.second;
        for(int i=0;i<8;i++)
        {
            int rx = x+dx2[i],ry = y+dy2[i];
            if(rx>=0 && rx<=n+1 && ry>=0 && ry<=m+1 && !vis[rx][ry])
            {
                if(g[rx][ry] == '1') bfs1(rx,ry);
                else
                {
                    vis[rx][ry] = true;
                    q.push({rx,ry});
                }
            }
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        ans = 0;
        memset(vis,false,sizeof(vis));
        cin >> n >> m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >> g[i][j];
        bfs2();
        cout << ans << endl;
    }
    return 0;
}