Easy understood c++ code based on BFS


  • 0
    X

    i'am confused with the result -- output limit exceeded for a long time.. and finnally i found that i add a line which is "cout <<.. ".... mark and remaind myself

    class Solution {
    struct Position{
        int i;
        int j;
        Position(int x, int y) : i(x), j(y) {}
    };
    public:
    void spreadO2(int i, int j, vector<vector<char>> &board){
        queue<Position> scanQue;
        Position first(i, j);
        board[first.i][first.j] = 'P';
        scanQue.push(first);
    
        while(!scanQue.empty()){
            Position tmp = scanQue.front();
            scanQue.pop();
            if(tmp.j > 0 && board[tmp.i][tmp.j-1] == 'O'){
                Position next(tmp.i, tmp.j-1);
                board[tmp.i][tmp.j-1] = 'P';
                scanQue.push(next);
            }
            if(tmp.j < y-1 && board[tmp.i][tmp.j+1] == 'O'){
                Position next(tmp.i, tmp.j+1);
                board[tmp.i][tmp.j+1] = 'P';
                scanQue.push(next);
            }
            if(tmp.i > 0 && board[tmp.i-1][tmp.j] == 'O'){
                Position next(tmp.i-1, tmp.j);
                board[tmp.i-1][tmp.j] = 'P';
                scanQue.push(next);
            }
            if(tmp.i < x-1 && board[tmp.i+1][tmp.j] == 'O'){
                Position next(tmp.i+1, tmp.j);
                board[tmp.i+1][tmp.j] = 'P';
                scanQue.push(next);
            }
        }
    }
    
    
    void solve(vector<vector<char>> &board) {
        if(board.empty())
            return;
    
        x = board.size(), y = board[0].size();
    
        for(int i=0; i<y; i++)
            if(board[0][i] == 'O')
                spreadO2(0, i, board);
        if(x > 1){
            for(int i=0; i<y; i++)
                if(board[x-1][i] == 'O')
                    spreadO2(x-1, i, board);
        }
        for(int i=0; i<x; i++)
            if(board[i][0] == 'O')
                spreadO2(i, 0, board);
        if(y > 1){
            for(int i=0; i<x; i++)
                if(board[i][y-1] == 'O')
                    spreadO2(i, y-1, board);
        }
    
        for(int i=0; i<x; i++){
            for(int j=0; j<y; j++){
                if(board[i][j] == 'O')
                    board[i][j] = 'X';
                else if(board[i][j] == 'P')
                    board[i][j] = 'O';
            }
        }
    }
    private:
        int x, y;
    };

Log in to reply
 

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