[LintCode] Number of Islands

Problem

Given a boolean 2D matrix, find the number of islands.

Notice

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.

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]
]

return 3.

Solution

Flood Fill

class Solution {
private:
    int step[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
public:
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    void dfs(int x, int y, vector<vector<bool> > &grid, vector<vector<bool> > &canUse) {
        canUse[x][y] = false;
        
        for(int i = 0; i < 4; i++) {
            int newX = x + step[i][0];
            int newY = y + step[i][1];
            if (0 <= newX && newX < grid.size() && 0 <= newY && newY < grid[0].size() && canUse[newX][newY] && 
            grid[newX][newY]) {
                dfs(newX, newY, grid, canUse);
            }
        }
    }
    
    int numIslands(vector<vector<bool>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        
        vector<vector<bool> > canUse(grid.size(), vector<bool>(grid[0].size()));
        for(int i = 0; i < canUse.size(); i++) {
            for(int j = 0; j < canUse[i].size(); j++) {
                canUse[i][j] = true;
            }
        }
        
        int sum = 0;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] && canUse[i][j]) {
                    dfs(i, j, grid, canUse);
                    sum++;
                }
            }
        }
        
        return sum;
    }
};