1
$\begingroup$

Let's say we have given 2-dimensional maze in form of matrix, conisting only of the letters x and .. For example the following maze:

xxxxx 11111    .....
x...x 1...1    .xxx.
x.x.x 1.2.1    .x.x.
x...x 1...1    .x.x.
xxxxx 11111    .....

Let's group those elements, we will group x's only, such that two elements will be in one group if they share at least one of the 8 sides (4 regular and 4 diagonal). Up here is one way how to group them, now for each of those groups we want to check if they are forming closed figure (in the first maze there is closed figure and in the second there isn't because the area of x's isn't closed).

What I think for the solution

I was thinking that we should find 4 points first that are important for each figure, those are: the top right, top left, bottom left and bottom right nodes, and now check if there is path from the top right to top left and bottom right, from the top left to bottom left and from the bottom left to the bottom right. But, it turns out that this is not working always.

$\endgroup$

3 Answers 3

1
$\begingroup$

Label open space in same way you label the x's, if a set of x's touches more than one label it contains a closed space.

$\endgroup$
0
$\begingroup$

My solution might be a little more complicated but if I wanted to solve this I would check the boundaries of the maze first, if there are no . anywhere on the left side, right side top and bottom. If there are no .'s we could assume the figure is closed.

Another interesting way to determine if the figure is closed or open, we could iterate through each vertical slice of the figure checking if any of of the . are on a border or touch a . on the border we could consider that . open as well. After you could iterate up again checking if any .'s are now touching open .'s. Finally you could iterate down one last time checking if there are any orphaned .'s if that's the case, the figure contains a closed figure and the check fails.

$\endgroup$
1
  • $\begingroup$ This doesn't work. The goal is to determine whether a group of x's is closed. We can have an open group of x's in the middle, with x's around the four boundaries, and your algorithm in the first paragraph would give the wrong answer. $\endgroup$
    – D.W.
    Commented Sep 28, 2017 at 22:20
0
$\begingroup$

Add an "external" border marked with $*$ and with a single $\$$ in the top-left corner:

$******   $****** 
*xxxxx*   *.....*
*x...x*   *.xxx.*
*x.x.x*   *.x.x.*
*x...x*   *.x.x.*
*xxxxx*   *.....*
*******   *******

A maze has a closed shape if and only if there exists a point $.$ from which we cannot reach $\$$ "walking" through "$.$" or "$*$"

In order to find such a point simply apply a flood fill algorithm starting from $\$$ (and considering $*$ and $.$ as "white" to be filled).

For the two mazes of your example we get:

$FFFFFF   $FFFFFF 
FxxxxxF   FFFFFFF
Fx...xF   FFxxxFF
Fx.x.xF   FFxFxFF
Fx...xF   FFxFxFF
FxxxxxF   FFFFFFF
FFFFFFF   FFFFFFF

As you can see in the first case there are a bunch of "." that are not connected to $\$$ ... they lay undisturbed in a closed shape.

$\endgroup$
4
  • $\begingroup$ How would it work if we have more than one closed shapes that do are not connected with eachother, do we add extre elements to each shape? $\endgroup$ Commented Sep 29, 2017 at 8:42
  • $\begingroup$ @someone12321: The algorithm checks if there is at least one shape that is closed. You can also check/find distinct components applying the same flood fill algorithm for inner points. If from point $x$ you cannot reach point $y$, then they are in different closed shapes. $\endgroup$
    – Vor
    Commented Sep 29, 2017 at 9:05
  • $\begingroup$ Clever idea! However, I see one possible limitation... The question asks "given a group, determine whether that group has a closed shape" (by "group", it means "connected component of x's"), not "given a maze, determine whether that maze has a closed shape". At least, that's how I interpret it. So I think you might be answering a slightly different question. The maze might have several groups, some open and some closed, and this doesn't tell you how to tell which ones are open and which are closed. $\endgroup$
    – D.W.
    Commented Sep 29, 2017 at 15:55
  • $\begingroup$ @D.W. The algorithm can be easily adpated: just find the connected components (using the same flood fill algortihm, but treating the x as "white" to be filled); then emebed each component in a rectangle (completing the missing cells on the border with a x) and apply the algorithm in my answer. Another approach is: start from a point in a closed shape; find a reachable x and then apply the flood fill algorithm to the x and "extract" the corresponding enclosing shape. In all cases they are simple breadth-first searches applied several times to find connected components. $\endgroup$
    – Vor
    Commented Sep 29, 2017 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.