Given a boolean 2D matrix,0is represented as the sea,1is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Find the number of islands.

Have you met this question in a real interview?

Yes

Example

Given graph:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

return3.

class Solution {

public:

/**

 * @param grid a boolean 2D matrix

 * @return an integer

 */

int numIslands(vector<vector<bool>>& grid) {

    // Write your code here

    if (grid.empty() || grid[0].empty()) {

        return 0;

    }

    int cnt = 0;

    int n = grid.size();

    int m = grid[0].size();

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < m; ++j) {

            if (grid[i][j] == false) {

                continue;

            }

            ++cnt;

            bfs(grid, i, j);

        }

    }



    return cnt;

}





void bfs(vector<vector<bool>>& grid, int i, int j) {

    queue<pair<int, int>> q;

    grid[i][j] = false;

    q.push(make_pair(i, j));

    int n = grid.size();

    int m = grid[0].size();

    vector<vector<int>> dirs = {{1,0}, {-1,0}, {0,1}, {0, -1}};

    while (!q.empty()) {

        auto cur = q.front(); q.pop();

        for (auto& dir : dirs) {

            pair<int, int> next;

            next.first = cur.first + dir[0];

            next.second = cur.second + dir[1];

            if (next.first >= 0 && next.first < n

                && next.second >= 0 && next.second < m 

                && grid[next.first][next.second]) {

                    q.push(next);

                    grid[next.first][next.second] = false;

                }

        }

    }

}
};