算连接点以网格 [英] Count connected dots in a grid

问题描述

予有m×n个单元的网格。其中有些是打开和关闭状态。找到一个有效的算法来计算无连接。

I have a grid of m X n cells. Some of them are on and off state. Find an efficient algorithm to count the no of connections.

在连接前很多点，左，右，下仍然被认为是1个连接。

Many dots connected in top, left, right, bottom still be considered 1 connection.

推荐答案

扫描网格以某种顺序。当你达到一个单元格上，执行洪水填写的就可以了。

Scan your grid in some order. When you reach a cell that is on, perform a flood fill on it.

通过关闭填充每一个细胞。在您的颜色填充完成后，继续你的扫描。

"Fill" each cell by turning it off. After your flood fill is done, continue your scan.

在原始的网格连接的组件的数量等于所执行的次数倾倒填充

The number of connected components in the original grid equals the number of times you performed a flood fill.

这篇关于算连接点以网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！