迷宫中的计数区域

问题描述 投票:0回答:1

Maze

编写一个函数count_areas(diagonal_maze),该函数接受一个对角迷宫(作为字符串列表)并返回对角迷宫中的封闭区域数。我们假设迷宫的外围存在非对角线边界。

>`count_areas(["\//\\\\/", "\///\\\\", "//\\\\/\\", "\/\///"]) 
>12`

>'count_areas(["\/", "/\\"]) 
>4'

我们使每个\\只代表一个\,因为python语法\很特殊。

我的想法是看第一行,然后将其余的与第一行进行比较...。但是,似乎有太多条件要考虑。

有人可以澄清我的逻辑吗?

python image-processing area maze
1个回答
0
投票

这很容易使用不相交的集合数据结构解决:

为每个垂直或水平边界创建一个集合-单元之间的边界以及迷宫边缘周围的边界。

对于每个/单元,将其顶部和左侧的集合连接在一起,并对其底部和右侧的集合进行连接。

对于每个\单元,将其顶部和右侧的集合连接在一起,并将底部和左侧的集合连接在一起。

最后,算出剩下的套数-迷宫的每个区域都会有一个。

© www.soinside.com 2019 - 2024. All rights reserved.