C语言求解水坑问题

梦里梦外; 2022-03-16 18:38 221阅读 0赞

**主要思路：**  
1.用一个二维数组来存放用户从键盘输入的水滴分布矩阵；  
2.遍历整个二维数组，对有水滴存在的位置周围的8个方向进行递归搜索，判定是否存在相邻接的水滴，同时水坑数加1；  
**关键：**  
本程序的关键在于维数未知的二维数组作为函数形参时的参数声明问题。可参考代码中的解决方式。

/*---------------------------------------------------
    功能：计算水坑个数
    首行输入矩阵行数和列数m, n；
    接下来输入水滴分布二维矩阵,'W'表示有水，'.'表示干燥；
    判定规则为：八个方向相连的水滴可构成一个水坑，若某水滴
    与其余水滴都不相连，则其单独构成一个水坑。
    输入示例：
    10 12
    W........WW.
    .WWW.....WWW
    ....WW...WW.
    .........WW.
    .........W..
    ..W......W..
    .W.W.....WW.
    W.W.W.....W.
    .W.W......W.
    ..W.......W.
    输出示例：
    3
    -------------------------------------------------------
    Author: Zhang Kaizhou
    Date: 2019-3-11 17:57:12
    ------------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    
    void puddle_number(int m, int n, char a[m][n], int i, int j);
    
    int main(){
        int m, n, i, j, res = 0;
        scanf("%d %d", &m, &n);
        getchar();
        char a[m][n];
        for(i = 0; i < m; i++){
            for(j = 0; j < n; j++){
                scanf("%c", &a[i][j]);
            }
            getchar();
        }
        for(i = 0; i < m; i++){ // 遍历整个水滴分布矩阵，搜索水滴处其周围水滴分布情况
            for(j = 0; j < n; j++){
                if(a[i][j] == 'W'){ // 寻找到水滴，水坑数加1，并递归搜索器周围水滴情况
                    res++;
                    puddle_number(m, n, a, i, j);
                }
            }
        }
        printf("%d\n", res);
    
        return 0;
    }
    
    void puddle_number(int m, int n, char a[m][n], int i, int j){ // 递归搜索当前水滴个方向上的水滴情况
        int dir1, dir2;
        if(a[i][j] == 'W'){ // 若当前点有水，递归结束的条件
            a[i][j] = '.'; // 将当前点改为干燥，避免重复确认，程序进入死循环
            for(dir1 = -1; dir1 < 2; dir1++){ // 双重for()循环实现对八个方向的搜索确认
                for(dir2 = -1; dir2 < 2; dir2++){
                    if(i >= 0 && i <= m && j >= 0 && j <= n){
                        puddle_number(m, n, a, i + dir1, j + dir2); // 递归搜索
                    }
                }
            }
            return;
        }else{
            return;
        }
    }