Finding unreachable sections of a 2D map

Question

I don't want you to solve this problem for me, i just want to ask for some ideas.

This is the input below, and it represents a map. The 'x' represents land, and the dots - water. So with the 'x' you can represent 'islands' on the map.

xxx.x...xxxxx        
xxxx....x...x        
........x.x.x        
..xxxxx.x...x       
..x...x.xxx.x        
..x.x.x...x..        
..x...x...xxx        
...xxxxxx....        
x............ 

As you can see, there are some islands which are closed, i.e. if some boat is inside its territory, it won't be able to get out, for ex:

..xxxxx.     
..x...x.        
..x.x.x.        
..x...x.
..xxxxx.

And there are some open islands which is possible to get out of them, ex:

.xxxxx        
.x...x        
.x.x.x        
.xxx.x       

The problem is this: For a given NxM map like those above, calculate howm any of the islands are open, and how many are closed.

I repeat: I don't want you to solve it, just need some sugestions, ideas for solving. thanks

Answer 1

I think using the good old flood fill algorithm should tell you if from some point you can reach another point.

http://en.wikipedia.org/wiki/Flood_fill

Also, you may need to define better what you mean by inside and outside (I think).

Answer 2

Just make a connected graph from all the dots (mark them while connecting) and when finished - check if any of the graph nodes is in the perimeter. then pass on to the next unmarked dot.

There are some common known algorithms to create a connected graph....

Answer 3

You can read it into a matrix, and then search for . or x, and when you find a . or x, run a recursive function which searches for adjacent connections. When you finish, search for the next . or x that hasn't been analyzed yet and repeat.

Answer 4

I assume that by close you mean an island that contains at least one square of sea, from which one cannot get to the map's borders; and by open you mean any other island out there.

So, first discover which sea tiles are reachable from the map's borders - by using flood fill from any sea tile on the border and marking those you pass along. If there are any sea tiles left on the border, continue the flood fill from there.

Now that you have marked all the tiles reachable from the border, all the other sea tiles are enclosed by land. You can find for each one of those the island enclosing it (by say going north till detecting land), and use flood fill on the land tiles, to mark the land tiles belonging to the island.

This way you can count islands enclosing sea tiles - "closed" islands.

Every land tile left unmarked belongs to an "open" island. use flood fill again to count those.

Answer 5

Here are some simple labeling rules:

• Water is either open or close
• Edge is open water
• Water next to open water is open

Answer 6

flooding algorithm, or BFS