CODEWITHSUNDEEP
pythonimage-processingareamaze
JungleKing
JungleKing

Reputation: 1

Count Areas in a Maze

Maze

Write a function count_areas(diagonal_maze) that takes in a diagonal maze (as list of string) and returns the number of enclosed area in the diagonal maze. We assume that there are non-diagonal boundaries on the perimeter of the maze.

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

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

We make every \\ to represent only one \ because python syntax \ is special.

My idea is to look at the first row then compare the rest with the first.... However, it seems that there are too many conditions to consider.

Can someone clear up my logic?

Upvotes: 0

Views: 319

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

This is easily solved using a disjoint set data structure:

Create a set for each vertical or horizontal boundary -- the ones between cells, and the ones around the edge of the maze.

For each / cell, join the sets for its top and left sides, and join the sets for its bottom and right sides.

For each \ cell, join the sets for its top and right sides, and join the sets for the bottom and left sides.

Finally, count the number of sets you're left with -- there will be one for each area of the maze.

Upvotes: 1

Related Questions