C++ code with different way


  • 0
    S
    class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int i_len = board.size();
            for(int i=0; i<i_len; i++)
            {
                int j_len = board[i].size();
                for(int j=0; j<j_len; j++)
                    if(board[i][j] == 'O' && (i == 0 || i == (i_len-1) || j == 0 || j == (j_len-1)))
                        board[i][j] = 'F';
            }
    
            for(int i=1; i<i_len-1; i++)
            {
                int j_len = board[i].size();
                for(int j=1; j<j_len-1; j++)
                {
                    if(board[i][j] == 'X' || board[i][j] == 'F') continue; // final 'o'/'x' for sure
                    // for unknown 'o'
                    checkNeighborsAndFlip(board, i, j);
                } // for j
            } // for i
            
            for(int i=0; i<i_len; i++)
            {
                int j_len = board[i].size();
                for(int j=0; j<j_len; j++)
                    if(board[i][j] == 'F')
                        board[i][j] = 'O';
            }        
        }
        
        void checkNeighborsAndFlip(vector<vector<char>>& board, int row, int col)
        {
            vector<pair<int,int>> checks;
            bool isOpen = false;
            int i = row, j = col;
            checks.push_back(make_pair(i, j));
            board[i][j] = 'C'; // mark it to "to be checked"
            int pop_index = -1, push_index = 0;
            while (pop_index != push_index)  //BFS
            {
                pair<int, int> item = checks[++pop_index];
                i = item.first; j = item.second;
                
                check(board, i-1, j, checks, push_index, isOpen);
                check(board, i+1, j, checks, push_index, isOpen);
                check(board, i, j-1, checks, push_index, isOpen);
                check(board, i, j+1, checks, push_index, isOpen);
            }
            
            for(int ind=0; ind<=push_index; ind++)
            {
                i = checks[ind].first;
                j = checks[ind].second;
                if(isOpen)
                    board[i][j] = 'F';
                else
                    board[i][j] = 'X';
            }
        }
    
        void check(vector<vector<char>>& board, int i, int j, vector<pair<int,int>>& checks, int& push_index, bool& isOpen)
        {
                if(board[i][j] == 'F')
                    isOpen = true;
                else if(board[i][j] == 'O')
                {
                    checks.push_back(make_pair(i, j));
                    board[i][j] = 'C';
                    push_index++;
                }
                // skip the board[i][j] == 'C' which must be in the checks already
        }
    };

Log in to reply
 

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