如何在二维数组中从左上到右下查找填充度最低的空白位置（类泛洪填充算法实现）

Let’s fix your BFS approach to match that "evenly distributed from top-left to bottom-right" requirement for finding the least-filled (FilledBits = 0) spot. Your core idea of using BFS is on the right track—it’s perfect for simulating the flood-fill style traversal you need—but the original implementation has a few key issues we’ll address.

First, Let’s Break Down the Problems with Your Existing BFS #

• Wrong starting point: You initialized the queue with 0,3 instead of the top-left corner 0,0, which violates the "start traversal from the top-left" requirement.
• No visit tracking: Without marking nodes as visited, you’ll end up reprocessing the same positions repeatedly, leading to inefficiency and unexpected behavior.
• No stop condition: You kept traversing even after finding a valid blank spot, and didn’t properly record the target position.
• Suboptimal traversal order: Your left/right/up/down order doesn’t prioritize moving toward the bottom-right, which is part of your "evenly distributed" goal.

Solution 1: Find the First Reachable Blank (Closest to Top-Left) #

This matches the flood-fill logic you described—we start at 0,0, spread outward, and stop at the first un-filled spot (since BFS guarantees this is the closest/most prioritized position from the top-left).

'修正后的BFS：找到从左上出发最早可达的空白位置
Dim targetRow As Integer = -1
Dim targetCol As Integer = -1

' 初始化访问矩阵（防止重复处理节点，适配可变行长度）
Dim visited As List(Of List(Of Boolean)) = New List(Of List(Of Boolean))()
For Each row In Uniques
    visited.Add(New List(Of Boolean)(Enumerable.Repeat(False, row.Length)))
Next

' 用Tuple存储行列，比字符串分割更可靠
Dim queue As Queue(Of Tuple(Of Integer, Integer)) = New Queue(Of Tuple(Of Integer, Integer))()

' 从左上角(0,0)开始遍历
If Uniques.Length > 0 AndAlso Uniques(0).Length > 0 Then
    queue.Enqueue(Tuple.Create(0, 0))
    visited(0)(0) = True
End If

While queue.Count > 0 AndAlso targetRow = -1
    Dim current = queue.Dequeue()
    Dim row = current.Item1
    Dim col = current.Item2

    ' 检查当前位置是否是未填充的空白（目标）
    If FilledBits(row)(col) = 0 Then
        targetRow = row
        targetCol = col
        Exit While ' 找到目标后立即停止
    End If

    ' 按优先级添加邻接节点：优先向右、向下（贴合左上到右下的遍历方向），再向左、向上
    ' 向右
    If col + 1 < Uniques(row).Length AndAlso Not visited(row)(col + 1) Then
        visited(row)(col + 1) = True
        queue.Enqueue(Tuple.Create(row, col + 1))
    End If
    ' 向下
    If row + 1 < Uniques.Length AndAlso col < Uniques(row + 1).Length AndAlso Not visited(row + 1)(col) Then
        visited(row + 1)(col) = True
        queue.Enqueue(Tuple.Create(row + 1, col))
    End If
    ' 向左
    If col - 1 >= 0 AndAlso Not visited(row)(col - 1) Then
        visited(row)(col - 1) = True
        queue.Enqueue(Tuple.Create(row, col - 1))
    End If
    ' 向上
    If row - 1 >= 0 AndAlso col < Uniques(row - 1).Length AndAlso Not visited(row - 1)(col) Then
        visited(row - 1)(col) = True
        queue.Enqueue(Tuple.Create(row - 1, col))
    End If
End While

' 输出结果
If targetRow <> -1 AndAlso targetCol <> -1 Then
    Console.WriteLine($"找到填充度最低的位置：行[{targetRow}] 列[{targetCol}] 值为{Uniques(targetRow)(targetCol)}")
Else
    Console.WriteLine("所有位置都已填充")
End If

Key Improvements:

• Correct starting point: We begin at the top-left corner 0,0 to align with your traversal requirement.
• Dynamic visit tracking: A list of boolean lists adapts to rows with variable lengths (since your test code adds values dynamically).
• Early termination: We stop as soon as we find the first blank spot, which BFS guarantees is the closest to the top-left.
• Priority traversal: By adding right/down nodes first, we prioritize moving toward the bottom-right while maintaining full flood-fill coverage.

Solution 2: Find the Blank with the Least Surrounding Fills #

If "fill degree lowest" means the blank spot has the fewest filled neighbors (instead of just being the first reachable), use this version. It traverses all blank spots, counts their filled neighbors, and picks the one with the least fills (breaking ties by choosing the top-leftmost spot).

' BFS实现：找到周围填充数最少的空白位置
Dim minNeighborFills As Integer = Integer.MaxValue
Dim bestRow As Integer = -1
Dim bestCol As Integer = -1

' 初始化访问矩阵
Dim visited As List(Of List(Of Boolean)) = New List(Of List(Of Boolean))()
For Each row In Uniques
    visited.Add(New List(Of Boolean)(Enumerable.Repeat(False, row.Length)))
Next

Dim queue As Queue(Of Tuple(Of Integer, Integer)) = New Queue(Of Tuple(Of Integer, Integer))()
If Uniques.Length > 0 AndAlso Uniques(0).Length > 0 Then
    queue.Enqueue(Tuple.Create(0, 0))
    visited(0)(0) = True
End If

While queue.Count > 0
    Dim current = queue.Dequeue()
    Dim row = current.Item1
    Dim col = current.Item2

    ' 如果是空白位置，计算周围填充的数量
    If FilledBits(row)(col) = 0 Then
        Dim fillCount As Integer = 0
        ' 检查四个方向的填充状态
        ' 上
        If row - 1 >= 0 AndAlso col < FilledBits(row - 1).Length Then
            fillCount += FilledBits(row - 1)(col)
        End If
        ' 下
        If row + 1 < FilledBits.Length AndAlso col < FilledBits(row + 1).Length Then
            fillCount += FilledBits(row + 1)(col)
        End If
        ' 左
        If col - 1 >= 0 Then
            fillCount += FilledBits(row)(col - 1)
        End If
        ' 右
        If col + 1 < FilledBits(row).Length Then
            fillCount += FilledBits(row)(col + 1)
        End If

        ' 更新最优位置：填充数更少，或填充数相同但更靠近左上
        If fillCount < minNeighborFills OrElse (fillCount = minNeighborFills AndAlso (row < bestRow OrElse (row = bestRow AndAlso col < bestCol))) Then
            minNeighborFills = fillCount
            bestRow = row
            bestCol = col
        End If
    End If

    ' 添加邻接节点继续遍历（同优先级顺序）
    If col + 1 < Uniques(row).Length AndAlso Not visited(row)(col + 1) Then
        visited(row)(col + 1) = True
        queue.Enqueue(Tuple.Create(row, col + 1))
    End If
    If row + 1 < Uniques.Length AndAlso col < Uniques(row + 1).Length AndAlso Not visited(row + 1)(col) Then
        visited(row + 1)(col) = True
        queue.Enqueue(Tuple.Create(row + 1, col))
    End If
    If col - 1 >= 0 AndAlso Not visited(row)(col - 1) Then
        visited(row)(col - 1) = True
        queue.Enqueue(Tuple.Create(row, col - 1))
    End If
    If row - 1 >= 0 AndAlso col < Uniques(row - 1).Length AndAlso Not visited(row - 1)(col) Then
        visited(row - 1)(col) = True
        queue.Enqueue(Tuple.Create(row - 1, col))
    End If
End While

' 输出结果
If bestRow <> -1 AndAlso bestCol <> -1 Then
    Console.WriteLine($"找到填充度最低的位置：行[{bestRow}] 列[{bestCol}] 值为{Uniques(bestRow)(bestCol)}，周围填充数为{minNeighborFills}")
Else
    Console.WriteLine("所有位置都已填充")
End If

Why Your Original Forward/Reverse Traversals Didn’t Work #

Those approaches just iterate linearly through rows/columns, ignoring the flood-fill "spread" logic you need. They’ll skip over filled spots but won’t account for the even distribution from top-left to bottom-right—for example, if the top-left is filled, they’ll jump to the next column/row instead of exploring adjacent reachable spots.

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