How do you count the number of islands in a grid?
You walk over the grid, and every time you find a piece of land that you have not seen yet you count one island and you mark everything that belongs to it.
So what makes a group of land one island? The land cells have to be joined up, either by the sides or by the corners. That is the rule, and it is the detail that most people get wrong, because some versions of the question only count the sides.
the rule the neighbours of a cell
------------------- ---------------------------
only the sides up, down, left, right
the sides and the all eight around it
corners
And how do you mark the land? There are three ways. You change the land to water in the grid itself. You keep a set of the positions that you have visited. Or you put a marker in a separate visited grid. All three work, and the first one is the simplest to write.
And the shape of the answer matters. Every time you find a new piece of land that has not been marked, you have found a new island, so you add one to the answer and then you flood fill from that cell to mark everything that belongs to the same island.
the grid
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
there are 3 islands
And the complexity is O of rows times columns for the time, because every cell is looked at once or twice, and O of 1 for the space if you change the grid as you go, or O of rows times columns for the space if you keep a visited set.
So the rule to remember is this. One count for each piece of land that starts a new group, and then mark the whole group.
The last question in this topic shows the code.