C++. BFS . Clear mode you can learn


  • 2
    C
    /*****
    ****author: cxq
    ****weibo: http://weibo.com/chenxq1992
    ****/
    
    class Solution {
    public:
        typedef pair<int, int> state_t;
        int numIslands(vector<vector<char>> &grid) {
            if (grid.empty()) return 0;
            int count = 0;
            const int m = grid.size();
            const int n = grid[0].size();
            vector<vector<bool> > visited(m, vector<bool> (n, false));
            queue<state_t> q;
            auto is_valid = [&] (const state_t &s) {
                const int x = s.first;
                const int y = s.second;
                if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y])
                    return false;
                return true;
            };
            auto state_extend = [&] (const state_t &s) {
                vector<state_t> result;
                const int x = s.first;
                const int y = s.second;
                const state_t new_states[] = {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
                for (int i = 0; i < 4; ++i) {
                    if (is_valid(new_states[i])) {
                        result.push_back(new_states[i]);
                        visited[new_states[i].first][new_states[i].second] = true;
                    }
                }
                return result;
            };
            for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j) {
                    if(grid[i][j] == '0' || visited[i][j])
                        continue;
                    ++count;
                    state_t start = {i, j};
                    visited[i][j] = true;
                    q.push(start);
                    while (!q.empty()) {
                        auto tmp = q.front();
                        q.pop();
                        auto new_states = state_extend(tmp);
                        for (auto &s : new_states) q.push(s);
                    }
                }
            return count;
        }
    };

Log in to reply
 

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