How do I find the optimal wall to tear down in a maze to generate the largest area?
algorithm, graph-theory, language-agnostic
Solution
Union-find seems like an appropriate algorithm here.
Just loop through the grid and union each non-wall cell with its non-wall neighbours.
Then loop through the sets to find the biggest one (this is the biggest room).
Then loop through the grid again and, for each wall, check the size of union-ing the different sides of the wall together (just record the size, don't actually perform the union). The biggest recorded union would indicate the wall to break down to create the biggest room.
The running time of using known optimizations to union-find would be, for all remotely practical sizes of the grid, `O(rowCount*columnCount)` (linear).
Problem
I have a maze represented by a two dimensional array. ``` bool[][] maze = ... ``` where `maze[row][column]` is True if there is a wall at that location, or False if there is no wall at that location. The perimeter is always surrounded by walls. The goal is to identify the largest room and then find one cut point in the maze that, if you break down the wall at that point, will create the new largest room. Is there an algorithm that will find the wall to break that will create the largest room? Should this be modeled as a graph? EDIT: I was haphazardly throwing around the word room. A room is one or more non-walls, connected together. ``` ---------- | | | | |----| | | | ---------- maze = { {True, True, True, True, True}, {True, False, True, False, True}, {True, False, True, True, True}, {True, False, True, False, True}, {True, True, True, True, True} } ``` This diagram contains three rooms. Their areas are 3, 1, and 1. The optimal cut points would be either `(1,2)` or `(3, 2)`. Either of these would generate a room with an area of 5.