You are given a map as a grid grid. Each cell is the text "1" (land) or "0" (water).
An island is a group of land cells that are joined to each other left, right, up or down (not diagonally). Count the islands. You can assume that water surrounds the whole grid on all four sides.
Examples
Example 1:
Input: grid = [["1","0","0","1","1"],["1","0","0","0","1"],["0","0","1","0","0"],["0","1","1","0","1"]]
Output: 4
Explanation: There are four islands: the two cells on the left, the three cells at the top right, the three cells in the lower middle, and the single cell in the bottom right corner.
Example 2:
Input: grid = [["0","0"],["0","0"]]
Output: 0
Explanation: There is only water.
Example 3:
Input: grid = [["1","1","1"],["0","1","0"],["1","1","1"]]
Output: 1
Explanation: The land has the shape of the letter H. All of it is joined, so it is one island.