C#中求解二维矩阵最大4连通0元素区域的技术问题咨询

要找出矩阵中最大的4连通0区域，深度优先搜索（DFS） 或 广度优先搜索（BFS） 是最可靠的方案，能覆盖所有连通情况，包括同一行/列的连续区域。核心逻辑是：遍历矩阵每个元素，遇到未访问的0时，探索其所有上下左右连通的0，统计区域大小，同时标记已访问的位置避免重复计算。

代码实现（DFS版本） #

using System;

class Program
{
    static void Main()
    {
        // 示例输入矩阵
        int[,] matrix = {
            {1,1,1,0,0,0,0,1,1,1},
            {1,0,1,0,0,0,0,1,1,1},
            {1,0,1,1,1,1,1,0,1,1},
            {1,0,1,1,1,1,1,0,1,1},
            {1,0,1,1,1,1,1,1,1,1},
            {1,1,1,0,0,1,1,1,1,1},
            {1,1,1,0,0,1,1,1,1,1}
        };

        int rows = matrix.GetLength(0);
        int cols = matrix.GetLength(1);
        bool[,] visited = new bool[rows, cols];
        int maxArea = 0;

        // 遍历矩阵每个元素
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                // 遇到未访问的0，计算连通区域大小
                if (matrix[i,j] == 0 && !visited[i,j])
                {
                    int currentArea = DFS(matrix, visited, i, j, rows, cols);
                    maxArea = Math.Max(maxArea, currentArea);
                }
            }
        }

        Console.WriteLine($"最大4连通0区域大小：{maxArea}"); // 输出8
    }

    // 深度优先搜索，返回当前连通区域的大小
    static int DFS(int[,] matrix, bool[,] visited, int i, int j, int rows, int cols)
    {
        // 边界检查：超出矩阵范围、已访问、不是0，返回0
        if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i,j] || matrix[i,j] != 0)
        {
            return 0;
        }

        // 标记当前位置为已访问
        visited[i,j] = true;

        // 递归探索上下左右四个方向，累加区域大小
        return 1 + DFS(matrix, visited, i-1, j, rows, cols) // 上
                 + DFS(matrix, visited, i+1, j, rows, cols) // 下
                 + DFS(matrix, visited, i, j-1, rows, cols) // 左
                 + DFS(matrix, visited, i, j+1, rows, cols); // 右
    }
}

关键说明 #

1. 访问标记矩阵：visited 用来记录已经处理过的0元素，防止重复统计同一个区域。
2. DFS递归逻辑：每次遇到有效的0，就标记为已访问，然后递归检查上下左右四个方向的相邻元素，累加所有连通的0数量。
3. 边界处理：确保递归不会超出矩阵范围，同时跳过已访问的元素和非0元素。

如果担心递归深度过大（比如矩阵非常大），可以改用BFS版本（用队列实现），逻辑类似，只是把递归换成队列遍历：

代码实现（BFS版本） #

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[,] matrix = {
            {1,1,1,0,0,0,0,1,1,1},
            {1,0,1,0,0,0,0,1,1,1},
            {1,0,1,1,1,1,1,0,1,1},
            {1,0,1,1,1,1,1,0,1,1},
            {1,0,1,1,1,1,1,1,1,1},
            {1,1,1,0,0,1,1,1,1,1},
            {1,1,1,0,0,1,1,1,1,1}
        };

        int rows = matrix.GetLength(0);
        int cols = matrix.GetLength(1);
        bool[,] visited = new bool[rows, cols];
        int maxArea = 0;

        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (matrix[i,j] == 0 && !visited[i,j])
                {
                    int currentArea = BFS(matrix, visited, i, j, rows, cols);
                    maxArea = Math.Max(maxArea, currentArea);
                }
            }
        }

        Console.WriteLine($"最大4连通0区域大小：{maxArea}");
    }

    static int BFS(int[,] matrix, bool[,] visited, int i, int j, int rows, int cols)
    {
        Queue<Tuple<int, int>> queue = new Queue<Tuple<int, int>>();
        queue.Enqueue(Tuple.Create(i, j));
        visited[i,j] = true;
        int area = 0;

        // 上下左右四个方向的偏移量
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            int x = current.Item1;
            int y = current.Item2;
            area++;

            // 遍历四个方向
            for (int k = 0; k < 4; k++)
            {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >=0 && nx < rows && ny >=0 && ny < cols && !visited[nx, ny] && matrix[nx, ny] ==0)
                {
                    visited[nx, ny] = true;
                    queue.Enqueue(Tuple.Create(nx, ny));
                }
            }
        }

        return area;
    }
}

这两种方法都能正确处理同一行、同一列或任意形状的连通区域，示例中的顶部8个0区域会被完整统计，最终得到最大值8。

内容的提问来源于stack exchange，提问作者Gepcho