洪水填充算法

Flood fill is an algorithm mainly used to determine a bounded area connected to a given node in a multi-dimensional array. It is a close resemblance to the bucket tool in paint programs.

泛洪填充是一种算法，主要用于确定连接到多维数组中给定节点的有界区域。 它与绘画程序中的存储桶工具非常相似。

The most approached implementation of the algorithm is a stack-based recursive function, and that’s what we’re gonna talk about next.

该算法最常用的实现是基于堆栈的递归函数，这就是我们接下来要讨论的内容。

它是如何工作的？ (How does it work?)

The problem is pretty simple and usually follows these steps:

该问题非常简单，通常按照以下步骤操作：

1. Take the position of the starting point.
   取得起点位置。

2. Decide wether you want to go in 4 directions (N, S, W, E) or 8 directions (N, S, W, E, NW, NE, SW, SE).

   确定是否要沿4个方向( N，S，W，E )或8个方向( N，S，W，E，NW，NE，SW，SE )移动。

3. Choose a replacement color and a target color.
   选择替换颜色和目标颜色。
4. Travel in those directions.
   朝那些方向旅行。
5. If the tile you land on is a target, reaplce it with the chosen color.
   如果您着陆的瓷砖是目标，请使用选定的颜色对其进行重新装饰。
6. Repeat 4 and 5 until you’ve been everywhere within the boundaries.
   重复4和5，直到到达边界内的任何地方。

Let’s take the following array as an example:

让我们以以下数组为例：

The red square is the starting point and the gray squares are the so called walls.

红色正方形是起点，灰色正方形是墙。

For further details, here’s a piece of code describing the function:

有关更多详细信息，这是一段描述该功能的代码：

int wall = -1;void flood_fill(int pos_x, int pos_y, int target_color, int color){     if(a[pos_x][pos_y] == wall || a[pos_x][pos_y] == color) // if there is no wall or if i haven't been there      return;                                              // already go back      if(a[pos_x][pos_y] != target_color) // if it's not color go back      return;      a[pos_x][pos_y] = color; // mark the point so that I know if I passed through it.       flood_fill(pos_x + 1, pos_y, color);  // then i can either go south   flood_fill(pos_x - 1, pos_y, color);  // or north   flood_fill(pos_x, pos_y + 1, color);  // or east   flood_fill(pos_x, pos_y - 1, color);  // or west      return;}

As seen above, my starting point is (4,4). After calling the function for the start coordinates x = 4 and y = 4, I can start checking if there is no wall or color on the spot. If that is valid i mark the spot with one “color” and start checking the other adiacent squares.

如上所述，我的出发点是(4,4)。 在调用了起始坐标x = 4和y = 4的函数之后，我可以开始检查当场是否没有墙壁或颜色。 如果有效，则用一种“颜色”标记该斑点，然后开始检查另一种正方形。

Going south we will get to point (5,4) and the function runs again.

向南走，我们将指向(5,4)，函数再次运行。

锻炼问题 (Excercise problem)

I always considered that solving a (or more) problem/s using a newly learned algorithm is the best way to fully understand the concept.

我一直认为，使用新近学习的算法解决一个(或多个)问题是充分理解该概念的最佳方法。

So here’s one:

所以这是一个：

Statement:

声明：

In a bidimensional array you are given n number of “islands”. Try to find the largest area of an island and the corresponding island number. 0 marks water and any other x between 1 and n marks one square from the surface corresponding to island x.

在二维数组中，将为您提供n个“岛” 。 尝试找到一个岛的最大面积和相应的岛号。 0表示水，1到n之间的其他x表示离岛x对应的表面一个正方形。

Input

输入值

• n - the number of islands.

  n-岛屿数。

• l,c - the dimensions of the matrix.

  l，c-矩阵的尺寸。

• the next l lines, c numbers giving the lth row of the matrix.

  接下来的l行， c给出矩阵的第l行。

Output

输出量

• i - the number of the island with the largest area.

  i-面积最大的岛屿数目。

• A - the area of the i‘th island.

  A-第i岛的面积。

Ex:

例如：

You have the following input:

您有以下输入：

2 4 40 0 0 10 0 1 10 0 0 22 2 2 2

For which you will get island no. 2 as the biggest island with the area of 5 squares.

为此，您将获得岛屿编号。 2个最大的岛屿，面积为5平方。

提示 (Hints)

The problem is quite easy, but here are some hints:

这个问题很容易，但是这里有一些提示：

1. Use the flood-fill algorithm whenever you encounter a new island.2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).

翻译自:

洪水填充算法