“| 型连续块”——岛屿数量BFS+递归解法

记录一下23自命题真题压轴题——“岛屿数量”(仅作参考，大佬勿喷)

问题题目

一个矩形数字阵列，由数字0和 2 组成。其中，由2 组成的“|型连续块”定义为:如数字2 的上下左右中有2 则为同一个“型连续块”，求给定的矩形阵列中“| 型连续块”的个数。
例如阵列:
02220
22002
00200
该阵列中有3个“型连续块”。输入: m行n列由0和2组成的矩形数字阵列 (m200，n≤200);输出:“|型连续块”的个数

算法分析：

输入：

第一行输入矩阵的行数m和列数n，并用空格隔开。
随后依次输入各行元素，用空格隔开

核心：

 这里的2其实表示的是岛屿，0表示的是水，题目其实和力扣200题“岛屿数量” 一样，
 此处我加入了可以运行的main函数，具体方法注释应该讲的挺清晰的了。
 很有趣的一道题

c语言源码：

#include <stdio.h>
#include <stdlib.h>

int numIslands(char** arr, int m, int n);
void infect(char** arr, int i, int j, int m, int n);

int main() {
    char **arr;
    int m, n;
    scanf("%d%d", &m, &n);  ///输入m行n列的值
    ///动态申请空间
    arr =  (char **) malloc(sizeof (char*)*m); ///申请m行的内存
    int i, j, tmp;
    for (i=0; i<n; i++)
    {
        arr[i] = (char*) malloc(sizeof(char)*n);    ///每行申请n列个空间
    }
    ///输入矩阵
    for (i=0; i<m; i++)
    {
        for (j=0; j<n; j++)
        {
            scanf("%d", &tmp);
            arr[i][j] = tmp + '0';  ///将输入的数字转为字符存入数组中
        }
    }
    ///输出矩阵
    for (i=0; i<m; i++)
    {
        for (j=0; j<n; j++)
        {
            putchar(arr[i][j]);
        }
        printf("\n");
    }
    ///输出结果
    printf("%d", numIslands(arr, m ,n));
    return 0;
}

///只能接受动态分配的空间,不能直接传输一个静态二维数组过来
int numIslands(char** arr, int m, int n) {
    int i, j, count=0;  ///count表示岛屿数量
    for (i=0; i<m; i++)
    {
        for (j=0; j<n; j++)
        {
            if (arr[i][j] == '2')   //如果是岛屿
            {
                infect(arr, i, j, m ,n);    //BFS检测附近的岛屿
                count++;    //岛屿数量+1
            }
        }
    }
    return count;   //返回岛屿的数量
}

void infect(char** arr, int i, int j, int m, int n)
{
    //若不是岛屿则直接return
    if (i<0 || j<0 || i>=m || j>=n || arr[i][j]=='0')
        return;
    arr[i][j] = '0';    //若是岛屿，则将其变为水
    //并将其上下左右的岛屿都遍历一遍(也就是广度优先搜索BFS)
    infect(arr, i-1, j, m ,n);
    infect(arr, i+1, j, m ,n);
    infect(arr, i, j-1, m ,n);
    infect(arr, i, j+1, m ,n);
}

输入

3 5 
0 2 2 2 0
2 2 0 0 2
0 0 2 0 0

输出

02220
22002
00200
3