0
我有陈述那样的CS问题:(“”或者(切割)或‘#’(不切断))如何在隐式图中找到多个连通的组件?
鉴于纸与一些细胞切下,由字符表示的片材,我需要找出将会形成多少片。
实施例:
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
回答为上面的例子中是5 。
一个片将形成:
....
.##.
....
两片将形成:
....
.#..
..#.
常识表明我找到一种方法,以表示与曲线图的片材(各数字符号是顶点,并且如果它们共享一侧,则连接两个顶点)。但是,我不清楚该怎么做。我发现有隐式图(由返回给定顶点的所有邻居的函数定义的图)。像这样的功能在这种情况下实现是微不足道的。
现在的问题是:我应该如何修改DFS算法来查找这类图中的组件?