I tried a few different approaches to traversing the grid, such as finding the cells that are on the "seashore" of the island or trying to infer the number of islands by calculating how many times the rows and columns alternate between "X" and ".". Ultimately, I decided I was going to get nowhere until I worked out a solid algorithm to "walk" the map.
To do that, I used "pseudocode". "Old School" techniques like pseudocode don't get much respect these days, but it certainly worked for me! I also made a copy of the map in the Windows Snipping Tool so I could draw lines to visualize what the code was doing. This turned out to be the secret that made it possible to figure out exactly what steps had to be in the program. Once the pseudocode was solid, translating it to real VB.NET code was fairly easy. In fact, the code ran the first time. It turned out to have only one bug left in it that I didn't catch in the pseudocode testing. Here's a shot of the testing process:
--------
Click Here to display the illustration
Click the Back button on your browser to return
--------
And here's the pseudocode that worked for me. It consists of one main loop and one recursive subroutine. Things like Increment and EndOfMap were coded as separate subroutines, just to keep the code easier to create and read. Increment moves across the columns and then down the rows until it reaches the last cell in the map.
Start(0,0)
Do
UnMarked Land?
Yes
Add 1 to Island Count
LookAround
No
Fall Through
Increment
EndOfMap?
Yes
ReportIslands
Stop
No
Fall Through
Loop
LookAround:
Save Location
Land, MarkIt
GoLeft
UnMarked Land?
Yes, LookAround
No, GoRight
GoDown
UnMarked Land?
Yes, LookAround
No, GoUp
GoRight
UnMarked Land?
Yes, LookAround
No, GoLeft
GoUp
UnMarked Land?
Yes, LookAround
No, GoDown
Restore Location
Exit Lookaround
The technique to successfully walk the map turned out to be "recursion". Here's the first few lines of the recursive subroutine from the program:
Friend Sub LookAround()
Dim SaveRGL, SaveCGL As Int16
MarkGridCell()
'Save State
SaveRGL = RGL : SaveCGL = CGL
' Go Left
CGL -= 1
If UnMarkedLand() Then
' Note that the statement
' below calls the same
' subroutine that it is in.
' That makes it "recursive".
LookAround()
Else
CGL += 1 ' Go Right Again
End If
One way to visualize this is to think of it as subroutines that are nested as deep as necessary, like this:
Top
...
Sub LookAroundChild1
...
Sub LookAroundChild2
and so forth
until some condition
is met.
End Sub
End Sub
End Sub
But since we don't actually have different subroutines, the VB.NET compiler has to generate code that "saves" everything about the subroutine and then starts over at the top. In this program, this happens for every cell in the grid that has an "X" in it. In a typical 10 x 10 map, it's common for the recursion here to be nested twenty or thirty levels deep. For more about recursion, you might want to read this article I wrote a few years ago: VB.NET and Recursion.
In my code above, I declared the "row grid locator" - RGL - and the "column grid locator" - CGL as global variables so I wouldn't have to keep passing them between subroutines and functions. I saved the state of these when I started recursively testing any cell to see whether other "Land" cells were present next to the current one because these are the key variables used in that process.
One final refinement made it easier to make sure that everything was working the way it should: Mark the islands with highlighting and their "number" so it would be easy to verify that islands are actually being counted correctly. That's done on the next page.