Have Geek Brain

Algorithm. Determine the shape of the two sectors, outlined in an arbitrary way, and then fill in one

NOTE. This is a tricky problem for anyone who loves logic problems, etc.

Consider a rectangular two-dimensional grid with a height H and a width W. Each space in the grid has a value, either 0

1

or 2

. Initially, every space in the grid is there 0

, except for gaps along each of the four edges, which are initially composed of 2

.

Next, consider an arbitrary path of adjacent (horizontally or vertically) mesh spaces. The path begins with 2

and ends on another 2

. Each space along the path has a view 1

.

The path divides the grid into two "sectors" of spaces 0

. There is an object that rests on an indefinite space 0

. A "sector" that does NOT contain an object must be completely filled 2

.

Define an algorithm that determines the spaces to come 2

from 0

, given an array (list) of values ​​( 0

, 1

or 2

) that correspond to 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 (originally a 2

). The item at index 1 contains the space value in the grid, which is in the left column, second from the top, and so on. The H index element contains the value of the space in the grid, which is in the top row but second from the left, and so on.

Once the algorithm ends and the empty "sector" is completely filled with 2

s, the SAME algorithm should be sufficient to re-execute the same process. Second (and time), the path is still executed from 2

to the other 2

, through the spaces 0

, but the "grid" is smaller, because those that 2

are surrounded by others 2

cannot be touched by the path (since the path goes along the spaces 0

).

I thank everyone who is able to understand this for me very much. It doesn't have to be in a particular programming language; actually enough pseudocode or just English. Thanks again! If you have any questions, just leave a comment and I will point out what to point out.

+2


a source to share


1 answer


It looks to me like a basic fill fill algorithm would do the job:

  • Scan your array for the first 0

    one you find, and then start filling the fill from there by filling the area with 0

    some other number, say 3

    - this will represent one of your "sectors".
  • After that, scan again 0

    and fill the fill from there, filling 4

    this time.
  • During both fillings, you can check whether you have found your object or not; depending on what you dial, on time, keep track of this number.
  • After both fills are finished, check which numbered area the object was in - fill that area again, this time with 0

    .
  • The flood will fill the other numbered area 2

    and you're done.

This will work for any mesh configuration as long as there are exactly two sectors 0

that are disconnected from each other; therefore, reapplying the same algorithm is performed at any time.



Edit: Minor changes to keep the fill or two -

  • If you didn't find your object in the first fill fill, you can assume that there is another sector in it, so you just re-fill the current number 2

    and leave the other sector separate (since it is already 0

    full).
  • Alternatively, if you find an object in the first fill of the fill, you can directly fill another wedge 2

    and then fill the first wedge again 0

    .
+3


a source






More articles:


All Articles