C++ Bredth-first-search solution


  • 0
    X
    class Solution {
    public:
        void solve(vector<vector<char> >& board) {
            if (board.size() == 0) return;
            int m = board.size();
            int n = board[0].size();
            vector<vector<bool> > visited(m, vector<bool>(n, false));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == 'O' && visited[i][j] == false && insideTheCircle(i, j, m, n)) {
                        vector<pair<int, int> > orders;
                        if (! bfs(i, j, m, n, board, orders, visited) )
                            continue;
                        for (auto p : orders) {
                            board[p.first][p.second] = 'X';
                        }
                    }
                }
            }
        }
        
        bool insideTheCircle(int i, int j, int m, int n) {
            return (i > 0) && (i < m-1) && (j > 0) && (j < n-1);
        }
        
        bool bfs(int i, int j, int m, int n, vector<vector<char> >& board, vector<pair<int, int> >& orders, vector<vector<bool> >& visited) {
            queue<pair<int, int> > q;
            q.push(make_pair(i, j));
            visited[i][j] = true;
            int hasBoundaryO = false;
            while (!q.empty()) {
                auto p = q.front(); q.pop();
                i = p.first;
                j = p.second;
                orders.push_back(p);
                //access right
                if (j + 1 < n && visited[i][j+1] == false && board[i][j+1] == 'O') {
                    visited[i][j+1] = true;
                    if (insideTheCircle(i, j+1, m, n))
                        q.push(make_pair(i, j+1));
                    else // I made a mistake here: if there is boundary zero, do not directly return, still iterate all Oes
                         // but keep a flag to judge whether the area covered using BFS is valid
                        hasBoundaryO = true;
                }
                //access down
                if (i + 1 < m && visited[i+1][j] == false && board[i+1][j] == 'O') {
                    visited[i+1][j] = true;
                    if (insideTheCircle(i+1, j, m, n))
                        q.push(make_pair(i+1, j));
                    else
                        hasBoundaryO = true;
                }
                //access up
                if (i - 1 >= 0 && visited[i-1][j] == false && board[i-1][j] == 'O') {
                    visited[i-1][j] = true;
                    if (insideTheCircle(i-1, j, m, n))
                        q.push(make_pair(i-1, j));
                    else
                        hasBoundaryO = true;
                }
                //access left
                if (j - 1 >= 0 && visited[i][j-1] == false && board[i][j-1] == 'O') {
                    visited[i][j-1] = true;
                    if (insideTheCircle(i, j-1, m, n))
                        q.push(make_pair(i, j-1));
                    else
                        hasBoundaryO = true;
                }
            }
            return !hasBoundaryO;
        }
    };

Log in to reply
 

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