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

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.