Problem Explanation:

The problem is asking to count the number of islands in a given grid map. In this context, an island is defined as a group of '1's (land) connected either horizontally or vertically and is surrounded by '0's (water). Both diagonally adjacent lands are not considered connected. We are also given that all four sides of the grid are surrounded by water.

For example, consider this grid:

1
2
311000
411000
500100
600011

In the above grid, we have three islands. Two islands are at the upper part of the grid and one island is at the lower right corner.

Solution Approach:

The key to solving this problem is to recognize that it is a graph traversal problem. Specifically, we will use the Breadth-First-Search (BFS) algorithm to traverse the grid. Whenever we encounter land ('1'), we increment our island count and start a BFS to mark all the connected land as visited. Once all the land connected to the current piece of land is marked visited, we move on to the next piece of land in the grid until the entire grid is traversed.

Let's try to understand this approach with a simple example. Let's say we have the following grid:

1
2
311000
411000
500100
600011

• Initially, the island count is 0.

• We start traversing the grid from the top-left corner. When we first encounter '1', we increment the island count to 1.

• We then begin a BFS to mark all land that is directly horizontally or vertically connected to this piece of land as visited. After visiting all, we update the grid as:

  1
  2
  322000
  422000
  500100
  600011

  where '2' denotes visited land.

• We continue traversing the grid. When we encounter the next '1', we once again increment our island count to 2 and start a BFS:

  1
  2
  322000
  422000
  522100
  600011

• The same process continues until we traverse the entire grid. The final island count is 3, which is the solution to this problem.

Solution:

C++ Solution:

1
2cpp
3class Solution {
4 public:
5  int numIslands(vector<vector<char>>& grid) {
6    const int m = grid.size();
7    const int n = grid[0].size();
8    // Define four directions to visit: right, down, left, up.
9    const vector<int> dirs{0, 1, 0, -1, 0};
10    int islandCount = 0;
11
12    // Lambda function for bfs.
13    // We will use lambda expression to declare BFS inside function.
14    auto bfs = [&](int r, int c) {
15      queue<pair<int, int>> q{{{r, c}}};
16      // Mark the current land as visited.
17      grid[r][c] = '2';
18      
19      // Continue until there is no land to visit.
20      while (!q.empty()) {
21        const auto [i, j] = q.front();
22        q.pop();
23
24        // Visit all four adjacent lands.
25        for (int k = 0; k < 4; ++k) {
26          const int x = i + dirs[k];
27          const int y = j + dirs[k + 1];
28          
29          // If the land is out of grid or it's water or visited land, skip.
30          if (x < 0 || x == m || y < 0 || y == n || grid[x][y] != '1')
31            continue;
32          
33          // If it's unvisited land, add it to the queue.
34          q.emplace(x, y);
35          // Mark the land as visited.
36          grid[x][y] = '2';
37        }
38      }
39    };
40
41    // Traverse the grid.
42    for (int i = 0; i < m; ++i)
43      for (int j = 0; j < n; ++j)
44        // If it's unvisited land, increment the islandCount and start bfs.
45        if (grid[i][j] == '1') {
46          bfs(i, j);
47          ++islandCount;
48        }
49
50    return islandCount;
51  }
52};

Note: For other languages' solution, please try to write it by yourself using similar approach. This will help you to understand the problem better as well as improve your problem solving skills.## Python Solution:

1
2python
3from collections import deque
4
5def numIslands(grid):
6    if not grid or not grid[0]: return 0
7    m,n = len(grid),len(grid[0])
8    islandCount = 0
9    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
10
11    def bfs(i, j):
12        queue = deque([(i, j)])
13        grid[i][j] = '2'
14        while queue:
15            x, y = queue.popleft()
16            for dx, dy in directions:
17                nx, ny = x + dx, y + dy
18                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
19                    queue.append((nx, ny))
20                    grid[nx][ny] = '2'
21
22    for i in range(m):
23        for j in range(n):
24            if grid[i][j] == '1':
25                bfs(i, j)
26                islandCount += 1
27
28    return islandCount

JavaScript Solution:

1
2javascript
3var numIslands = function(grid) {
4    if (!grid || grid.length === 0) return 0;
5    let islandCount = 0;
6    
7    for (let i = 0; i < grid.length; i++) {
8        for (let j = 0; j < grid[0].length; j++) {
9            if (grid[i][j] === '1') {
10                islandCount++;
11                bfs(grid, i, j);
12            }
13        }
14    }
15    return islandCount;
16};
17
18function bfs(grid, i, j) {
19    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] !== '1') return;
20    grid[i][j] = '2';
21    bfs(grid, i + 1, j);
22    bfs(grid, i - 1, j);
23    bfs(grid, i, j - 1);
24    bfs(grid, i, j + 1);
25}

Java Solution:

1
2java
3public int numIslands(char[][] grid) {
4    if (grid == null || grid.length == 0) {
5        return 0;
6    }
7    int m = grid.length, n = grid[0].length;
8    int islandCount = 0;
9
10    for(int i = 0; i < m; i++) {
11        for(int j = 0; j < n; j++) {
12            if(grid[i][j] == '1') {
13                bfs(grid, i, j);
14                islandCount++;
15            }
16        }
17    }
18    return islandCount;
19}
20
21void bfs(char[][] grid, int x, int y) {
22    int dx[] = {0, 0, -1, 1};
23    int dy[] = {-1, 1, 0, 0};
24    int m = grid.length, n = grid[0].length;
25
26    Queue<int[]> queue = new LinkedList<>();
27    queue.add(new int[] {x, y});
28    grid[x][y] = '2';
29
30    while(!queue.isEmpty()) {
31        int[] point = queue.remove();
32        int currX = point[0], currY = point[1];
33
34        for(int i = 0; i < 4; i++) {
35            int newX = currX + dx[i], newY = currY + dy[i];
36            if(newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == '1') {
37                queue.add(new int[] {newX, newY});
38                grid[newX][newY] = '2';
39            }
40        }
41    }
42}

With the above solutions, a count of islands in the two-dimensional grid map is found using the BFS algorithm in C++, Python, JavaScript, and Java. Each solution traverses the grid map, counting and tracking visited land to effectively find all islands. High-level languages have built-in data types, such as stack and queue, that help to implement the solution more easily.