C++, BFS + set, with explanation


  • 0
    Z

    It is straightforward to BFS each island. However, we need a way to encode each island, in order to tell whether they are distinct or not.

    For each island, a vector is used to store the relative locations of every point to the starting point. 
    If the starting point is (row, col), then for any point (r, c), a key value = (r-row)*50+c-col is 
    added into the island vector. 
    

    We can use a set (ordered set or tree set) to only keep unique vectors, and return its size. Another way is to sort and count all the unique island vectors.

    class Solution {
    public:
        int numDistinctIslands(vector<vector<int>>& grid) {
            set<vector<int>> islands;
            int m = grid.size(), n = grid[0].size();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) islands.insert(helper(grid, i, j));
                }
            }
            return islands.size();
        }
    private:
        vector<int> helper(vector<vector<int>>& grid, int row, int col) {
            int m = grid.size(), n = grid[0].size();
            vector<int> island;
            queue<pair<int, int>> myq;
            myq.push({row, col});
            grid[row][col] = 2;
            vector<int> dir = {-1,0,1,0,-1};
            while (!myq.empty()) {
                int z = myq.front().first, x = myq.front().second;
                myq.pop();
                for (int i = 0; i < 4; i++) {
                    int r = z+dir[i], c = x+dir[i+1];
                    if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
                        grid[r][c] = 2;
                        myq.push({r,c});
                        island.push_back((r-row)*50+c-col);
                    }
                }
            }
            return island;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.