使用 floodfill 算法计算 0 的个数

Question

我想用 floodfill 算法从二维数组中计算 0 和 1 的数量....但不幸的是......它显示了错误的结果。

我有一个这样的矩阵

0,1,1,0,1

1,0,1,1,0

1,0,1,1,0

1,0,1,1,0

1,0,1,1,0

它应该显示数字 0 = 10 和 1 =15

但它显示 0 = 4 和 1 = 21

这是我的代码

int[][] input;
public static int[,] reult;
public static int count = 0,col,row;
public Form1()
{
    InitializeComponent();
}

private void button1_Click(object sender, EventArgs e)
{
    string path;
    OpenFileDialog file = new OpenFileDialog();
    if (file.ShowDialog() == DialogResult.OK)
    {

        input = File.ReadLines(file.FileName)
                .Skip(0)
                .Select(l => l.Split(',')
                    .Select(n => int.Parse(n))
                    .ToArray())
                    .ToArray();

    }

    reult = JaggedToMultidimensional(input);

    int p = reult.GetLength(0); 
    int q = reult.GetLength(1); 
    row = p-1;
    col = q - 1;
    int one = p * q;
    int zero = apply(row, col);
    label1.Text = "" + zero;
    label2.Text = "" + (one - zero);

}

public T[,] JaggedToMultidimensional<T>(T[][] jaggedArray)
{
    int rows = jaggedArray.Length;
    int cols = jaggedArray.Max(subArray => subArray.Length);
    T[,] array = new T[rows, cols];
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            array[i, j] = jaggedArray[i][j];
        }
    }
    return array;
}

private static int apply(int x, int y)
{
    int currentColor = getValueAt(x, y);
    if (currentColor == 0)
    {
        visit(x, y);
        count++;

        if (x < row) apply(x + 1, y);
        if(y<col) apply(x, y + 1);
       if(x>0) apply(x - 1, y);
       if (y>0) apply(x, y - 1);
    }
    return count;
}

private static int getValueAt(int x, int y)
{
    if (x < 0 || y < 0 || x > row || y > col)
    {
        return -1;
    }
    else
    {
        return reult[x,y];
    }
}

private static void visit(int x, int y)
{
    reult[x,y] = 1;
}

Answer 1

int zero = apply(row, col);

在您的洪水填充算法中，您只在四个方向上移动并覆盖符合您标准的区域。幸运的是 [row,col] 索引有 0 并且它计算了 [row, col] 中的所有四个 0。现在想想如果 apply(row,col) 在那个 row, col 索引上有 1 会怎么样。

为了正确处理这件事，您需要遍历整个矩阵并在找到 array[i,j]==0

的地方调用 apply(i,j)

更改此行

int zero = apply(row, col);

到

int zero = 0;
for(int i=0; i<=row; i++)
{
   for(int j=0; j<=col; j++)
   {
       if(array[i][j]==0)
       {
          count =0;
          zero+= apply(row, col);
       }
   }
}

希望这对您有所帮助。

Answer 2

根据要求，您应该更改搜索条件以搜索 0 和 1。

你需要做的是在矩形内搜索，所以矩形的边界是搜索的限制。

即

int[] count = {0,0};

private static int apply(int x, int y)
{
    int currentColor = getValueAt(x, y);
    if (currentColor != -1)
    {
        visit(x, y);
        count[currentColor]++;

        if (x < row) apply(x + 1, y);
        if(y<col) apply(x, y + 1);
       if(x>0) apply(x - 1, y);
       if (y>0) apply(x, y - 1);
    }
    return count;
}

然后更改您的访问函数，将单元格设置为 -1 以避免访问它两次。

Answer 3

如果你愿意，你也可以使用 linq（我其实更喜欢）：

OpenFileDialog fileDialog = new OpenFileDialog();
            if (fileDialog.ShowDialog() == DialogResult.OK)
            {
                var lines = File.ReadLines(fileDialog.FileName);
                var splittedValues = lines.Where(l => !string.IsNullOrEmpty(l)).Select(l => l.Split(',')).SelectMany(l => l).ToList();
                var valCount = splittedValues.GroupBy(s => s).Select(s => new { val = s.Key, count = s.Count() }).ToList();     
            }

它会给你以下结果：

[0] { val= "0", count=10} [1] { val= "1", count=15}

使用 floodfill 算法计算 0 的个数

count number of 0 with floodfill algorithm

c#

algorithm

flood-fill