C++ implements LeetCode (200. Number of islands)

[LeetCode] 200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

The essence of this problem of finding the number of islands is to find the number of consecutive areas in the matrix. It is easy to think that we need to use depth-first search DFS to solve it. We need to create a visited array to record whether a certain position has been visited. For a position that is ‘1’ and has not been visited, recursively enters the number with ‘1’ on its upper, lower, left and right positions, assign the corresponding value of the visited to true, and continue to enter all its connected neighbor positions. In this way, all the numbers in this connected area can be found and the corresponding visited value is true. After finding the adjacent area, increase the result res by 1, and then continue to find the next position that is ‘1’ and has not been visited, and so on until the complete original array can be traversed to get the final result. The code is as follows:

Solution 1:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (() || grid[0].empty()) return 0;
        int m = (), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                helper(grid, visited, i, j);
                ++res;
            }
        }
        return res;
    }
    void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (x < 0 || x >= () || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
        visited[x][y] = true;
        helper(grid, visited, x - 1, y);
        helper(grid, visited, x + 1, y);
        helper(grid, visited, x, y - 1);
        helper(grid, visited, x, y + 1);
    }
};

Of course, the two pairs of good friends, DFS and BFS, which are similar to maze traversal, must be inseparable, so BFS will start. In fact, it is very simple. When traversing to '1' and the location has not been accessed, then call a BFS, and use the queue queue to implement it. Now add the current position to the queue, then perform a while loop, extract the header element of the queue, and traverse the four surrounding positions. If there is no cross-border, mark the neighbor position in visited as true, and add it to the queue and wait for the next traversal. See the code as follows:

Solution 2:

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (() || grid[0].empty()) return 0;
        int m = (), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                ++res;
                queue<int> q{{i * n + j}};
                while (!()) {
                    int t = (); ();
                    for (int k = 0; k < 4; ++k) {
                        int x = t / n + dirX[k], y = t % n + dirY[k];
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y]) continue;
                        visited[x][y] = true;
                        (x * n + y);
                    }
                }
            }
        }
        return res;
    }
};

Github synchronization address:

/grandyang/leetcode/issues/200