Number of Islands

• Lintcode : 433 / Leetcode : 200
• Level : Easy

Problem

Given a boolean 2D matrix, 0 is represented as the sea, 1 is 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.

Example
Example 1:

Input:
[
  [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]
]
Output:
3
Example 2:

Input:
[
  [1,1]
]
Output:
1

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(number of 1’s)
space: O(1)

Answer

class Solution {
public:
    int numIslands(vector<vector<bool>> &grid) {
        int numIslands = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j]) {
                    bfs(grid, i, j);
                    numIslands += 1;
                }
            }    
        }
        return numIslands;
    }

    void bfs(vector<vector<bool>> &grid, int i, int j){
        vector<vector<int>> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        queue<pair<int, int>> q;
        q.push({i, j});
        grid[i][j] = 0;
        while (!q.empty()) {
            pair<int, int> p = q.front(); q.pop();
            for (auto i : dir) {
                int x = i[0] + p.first;
                int y = i[1] + p.second;
                if (isValid(grid, x, y)) {
                    q.push({x, y});
                    grid[x][y] = 0;
                }
            }
        }
    }
    bool isValid(vector<vector<bool>> &grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()) return false;
        if (!grid[x][y]) return false;
        return true;
    }
};

tags: BFS

​