Simplified: There is an array

[[0,0,0,0,0], [0,1,1,0,0], [1,1,0,0,1], [0,1,0,0,1], [0,0,0,0,0]]

How to write closed areas, consisting of units in separate arrays? As an option

 [[0,1,1], [1,1,0], [0,1,0]] [[1], [1]]

I only have the option to run through all the rows of the original array, writing down the beginning and end of a sequence of units in a separate list, and after passing the next line compare overlaps. But most likely it is a bicycle crutch, and there is a decent rational solution. As always, you can not write the code, but hint how this is called correctly in bourgeois.

  • one
    In theory, you need a flood fill. If PHP has a bad recursion, organize the stack of deferred tasks manually. (The difference between the stack and the queue corresponds to a search in depth or width.) - VladD
  • Yes, already implemented the stack. Not a queue, since PHP also has problems with a queue-through-array = / There are no problems with recursion, there are problems with the head: I have already tried to use php again for purposes for which it was not intended. :) Thanks for the advice. - knes

2 answers 2

An interesting task, not encountered yet. Look like these islands: Islands in a two dimensional array

And I also remembered the rule of bypassing the labyrinth - always touch the wall with your right hand. You can not count 1, but “go” on zeros, touching with your right hand 1. When the route is closed, you go around the island. After that, the island is saved, the island 1 in the original array is reset. True, it can fail if there is a hole in the island, but there is another isolated sub-island in it :)

  • I liked the arsonist method more. He does not get tangled on the ring. - knes
  • ... but in php I stick in limiting recursion on large islands. Problem. = ( - knes
  • @knes, then another option: translate the array into a b / w image and use graphic libraries. For example imagemagick can select areas filled with the same color. Those. on large arrays php becomes inefficient, but with a 1-bit image it is quite possible to work. The task of selecting individual figures is constantly encountered in text recognition (OCR). And maybe return to the maze bypass? I do not know your task, but suddenly there holes are excluded? - Sergiks
  • In general, you can return to the one-row pass once:) There was a similar task recently: there are records of lengthy events (start, end), you need to find at any given time how many of them are simultaneously active. You can go along the line and memorize the "changes" of states: there were zeros, units became, or vice versa. And in the next line to compare these "events" with the previous one. Are the islands simple-convex, or can there be "labyrinths"? Just in one rectangular area can fit more than one island, theoretically. - Sergiks
  • the island inside the island is excluded, more precisely, we will consider it as one. But the bulge is a problem. They are usually pretty left shaped. Moreover, we still have to take into account their height, so it is impossible to translate to BW. Bypassing the labyrinth here is also bad because there are few islands and plenty of free space. Imagic I do not like, because it is in few places. In addition, as I have already noted, strained with “one color”: this is all, in fact, against a very heterogeneous background. :) - knes

The link provided by @Sergiks uses a recursive depth-search algorithm. If PHP has problems with the depth of recursion, you can do the same thing by searching for width . Typically, this algorithm is used to find a path, but it can also be used to identify elements belonging to one related area. It is enough to start the search at any point of the island, and at the moment when the queue becomes empty, the algorithm will mark all the cells belonging to the island as visited.

  • PHP is extremely reduced recursion - only 100 attachments. Actually, this is more than enough for the tasks for which it was created. Now I'm trying to rewrite Java, but that's another story. - knes