algorithm - MS paint 代码在面试中被问到

Question

我今天去面试，被问到了这个问题!

编写 MS Paint 程序。 N*N 像素区域。给定像素和颜色，将像素中的颜色更改为所需的颜色，如果相邻像素的颜色相同，则也更改它们。

我通过说我将采用 n* n 数组来接近它，并检查给定的像素并移动到相邻像素。例如给定的像素是 x,y 我会首先检查数组中 x,y 的颜色，然后查找 (x+1,y+1),(x+1,y),(x,y+1 ),(x-1,y),(x-1,y-1)...

但是面试官不高兴有人可以建议我另一种方法有更好的算法......具有更好的空间和时间复杂度!

Answer 1

面试官可能要求用洪水填充，用这么简单的方法是做不到的。

如果这是填充，对角线不算相邻。

最简单的泛洪填充是对数组中每个相邻像素的递归调用。在大网格上使用简单的方法很可能会耗尽堆栈。

正确的做法是从起始位置入队，然后出队，检查像素颜色是否还是源色，边走边扫描左右填充，将上下所有像素入队。继续直到排空队列。