第十四届蓝桥杯岛屿个数

题目描述：
小蓝得到了一副大小为 M×N 的格子地图，可以将其视作一个只包含字符 0（代表海水）和 1（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),…,(xk−1,yk−1)，其(x(i+1)%k,y(i+1)%k) 是由 (xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)，此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。
输入格式
第一行一个整数 T，表示有 T 组测试数据。
接下来输入 T 组数据。
对于每组数据，第一行包含两个用空格分隔的整数 M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是 0 或 1。

输出格式
对于每组数据，输出一行，包含一个整数表示答案。

数据范围
对于 30% 的评测用例，1≤M,N≤10。
对于 100% 的评测用例，1≤T≤10， 1≤M,N≤50 。
在这里插入图片描述

思路分析：
先从水里面开始八个方向来搜，如果搜到岛屿，就把岛屿扫一遍，如果一个岛屿a被其他岛屿围了起来，那么水肯定无法波及到它，思路就是这样，非常好想，只需要两步dfs就可以解决代码如下：
（需要注意的是本题要在地图最外层围上一层水，防止出现一开始上来技术岛屿导致水无法搜索）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };//上下左右
int dxx[] = { 0,1,0,-1,1,1,-1,-1 };
int dyy[] = { 1,0,-1,0,1,-1,1,-1 };//四面八方
bool st[55][55];//标记
int T, n, m, ans;
char g[55][55];
void ddfs(int x, int y)//扫陆地
{
        st[x][y] = 1;//标记
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (g[xx][yy] == '1' && xx >= 0 && yy >= 0 && xx <= n + 1 && yy <= m + 1 && !st[xx][yy])
            {
                ddfs(xx, yy);
            }
        }
}
void dfs(int x, int y)//海洋
{
        st[x][y] = 1;//标记
        for (int i = 0; i < 8; i++)
        {
      		int xx = x + dxx[i], yy = y + dyy[i];
      if (xx >= 0 && yy >= 0 && xx <= n + 1 && yy <= m + 1 && !st[xx][yy])
            {
                if (g[xx][yy] == '0') {
                    dfs(xx, yy);
                }
                else {
                    ddfs(xx, yy);
                    ans++;
                }
            }
        }
}
int main()
{
    cin >> T;
    while (T--)
    {
        ans = 0;//重置答案
        memset(st, 0, sizeof st);
        memset(g, '0', sizeof g);//重置标记和地图
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> g[i][j];
        dfs(0, 0);//从一开始搜索
        cout << ans << endl;
    }
    return 0;
}