编写一个函数count_areas(diagonal_maze),该函数接受一个对角迷宫(作为字符串列表)并返回对角迷宫中的封闭区域数。我们假设迷宫的外围存在非对角线边界。
>`count_areas(["\//\\\\/", "\///\\\\", "//\\\\/\\", "\/\///"])
>12`
>'count_areas(["\/", "/\\"])
>4'
我们使每个\\只代表一个\,因为python语法\很特殊。
我的想法是看第一行,然后将其余的与第一行进行比较...。但是,似乎有太多条件要考虑。
有人可以澄清我的逻辑吗?
这很容易使用不相交的集合数据结构解决:
为每个垂直或水平边界创建一个集合-单元之间的边界以及迷宫边缘周围的边界。
对于每个/
单元,将其顶部和左侧的集合连接在一起,并对其底部和右侧的集合进行连接。
对于每个\
单元,将其顶部和右侧的集合连接在一起,并将底部和左侧的集合连接在一起。
最后,算出剩下的套数-迷宫的每个区域都会有一个。