在网格上运行最佳洪水填充,同时仅限于非相交的正方形

Question

在网格上运行最佳洪水填充,同时仅限于非相交的正方形

Fre*_*nöw 8 algorithm optimization flood-fill

我需要通过获取其中的"元素"数量来优化网格,并尽可能地将其最小化.当我说元素时,我指的是该网格中的一个部分.这里基本上是"输入"在视觉上看起来像什么:

在此输入图像描述

想到的第一个解决方案是泛洪填充算法,但是,我有一个限制:所有元素必须有4个边,因此,所有元素必须是矩形.

我的第一个有限的方法简单包括逐个元素地循环输入网格,并检查最后一个新创建的元素是否是相同的颜色,并且具有与应该创建的元素相同的alpha - 如果是,则改为创建新元素时,它只会调整最后一个元素以进一步向下延伸1个块.

这是我正在做的一个伪代码示例:

element output_array();
element last_element = null;

for (int x = 0; x < grid_width; x++) {
    for (int y = 0; y < grid_height; y++) {
        color current_input_color = input_grid(x, y);

        if (last_element && last_element.x === x && last_element.color === current_input_color) {
            last_element.span_y++;
        } else {
            last_element = create_element(
                x,                   // element.x      (the x coordinate of the elements top left most grid space)
                y,                   // element.y      (the y coordinate of the elements top left most grid space)
                1,                   // element.span_x (the number of elements to span on the x axis)
                1,                   // element.span_y (the number of elements to span on the y axis)
                curent_input_color   // element.color
            );

            output_array.append(last_element);
        }
    }
}

Run Code Online (Sandbox Code Playgroud)

结果,我得到了这个(假设我输入了前一个网格):

在此输入图像描述