Algorithm: Determine shape of two sectors delineated by an arbitrary path, and then fill one.

Question

NOTE: This is a challenging problem for anybody who likes logic problems, etc.

Consider a rectangular two-dimensional grid of height H and width W. Every space on the grid has a value, either 0 1 or 2. Initially, every space on the grid is a 0, except for the spaces along each of the four edges, which are initially a 2.

Then consider an arbitrary path of adjacent (horizontally or vertically) grid spaces. The path begins on a 2 and ends on a different 2. Every space along the path is a 1.

The path divides the grid into two "sectors" of 0 spaces. There is an object that rests on an unspecified 0 space. The "sector" that does NOT contain the object must be filled completely with 2.

Define an algorithm that determines the spaces that must become 2 from 0, given an array (list) of values (0, 1, or 2) that correspond to the values in the grid, going from top to bottom and then from left to right. In other words, the element at index 0 in the array contains the value of the top-left space in the grid (initially a 2). The element at index 1 contains the value of the space in the grid that is in the left column, second from the top, and so forth. The element at index H contains the value of the space in the grid that is in the top row but second from the left, and so forth.

Once the algorithm finishes and the empty "sector" is filled completely with 2s, the SAME algorithm must be sufficient to do the same process again. The second (and on) time, the path is still drawn from a 2 to a different 2, across spaces of 0, but the "grid" is smaller because the 2s that are surrounded by other 2s cannot be touched by the path (since the path is along spaces of 0).

I thank whomever is able to figure this out for me, very very much. This does not have to be in a particular programming language; in fact, pseudo-code or just English is sufficient. Thanks again! If you have any questions, just leave a comment and I'll specify what needs to be specified.

Answer 1

Seems to me a basic flood fill algorithm would get the job done:

• Scan your array for the first 0 you find, and then start a flood fill from there, filling the 0 region with some other number, let's say 3 - this will label one of your "sectors".
• Once that's done, scan again for a 0, and flood fill from there, filling with a 4 this time.
• During both of the fills, you can be checking whether you found your object or not; whichever fill you find it during, keep track of that number.
• After both fills are done, check which numbered region had the object in it - flood fill that region again, back with 0 this time.
• Flood fill the other numbered region with 2, and you're done.

This'll work for any grid configuration, as long as there are exactly two 0 sectors that are disconnected from each other; so re-applying the same algorithm any number of times is fine.

Edit: Minor tweaks, to save you a flood-fill or two -

• If you don't find your object in the first flood-fill, you can assume that the other sector has it, so you just re-fill the current number with 2 and leave the other sector alone (since it's already 0-filled).
• Alternatively, if you do find the object in the first flood-fill, you can directly fill the other sector with 2, and then re-fill the first sector with 0.