C++, cont space, mark free O and replace those not marked - my easy to read code


  • 0
    P
    1. Find all O on the edge of the grid
    2. for each of the above, do BFS traversal (note, recursion will give for large tests) replacing 'O' with 'o' - marking free 'O' cells
    3. go over the whole grid and replace O=>X and o=>O

    The code:

    class Solution {
        int _rows;
        int _cols;
        
    public:
        void solve(vector<vector<char>> &board) {
            if(board.size()<3 || board[0].size()<3) return;
            
            _rows = board.size();
            _cols = board[0].size();
            
            for(int i=0; i<_rows;i++)
            {
                markFree(board,i,0);
                markFree(board,i,_cols-1);
            }
            for(int j=1;j<_cols-1;j++)
            {
                markFree(board,0,j);
                markFree(board,_rows-1,j);
            }
            
            for(int i=0; i<_rows;i++)
                for(int j=0;j<_cols;j++)
                {
                    if(board[i][j] == 'O') board[i][j] = 'X';
                    else if(board[i][j] == 'o') board[i][j] = 'O';
                }
        }
        
        void markFree(vector<vector<char>> &board, int I, int J)
        {
            stack<pair<int,int>> items;
            
            items.push(make_pair(I,J));
            
            while(!items.empty())
            {
                pair<int,int> p = items.top();
                items.pop();
                int i = p.first;
                int j = p.second;
                
                if(board[i][j] == 'X' || board[i][j]=='o') continue;
            
                if(board[i][j] == 'O') {
                    board[i][j] = 'o';
                }
            
                if(i < _rows-1) items.push(make_pair(i+1,j));
                if(j < _cols-1) items.push(make_pair(i, j+1));   
                if(i>0) items.push(make_pair(i-1,j));
                if(j>0) items.push(make_pair(i, j-1));
            }       
        }
    };

  • 0
    V

    cool, I use another hash table to record whether the position has been visited or not, your method are very efficiency


  • 0
    G

    nothing wrong with the code, but it is dfs not bfs


Log in to reply
 

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