top145-#130

[LionCoder4ever]

• dfs
• ans vector mark the outter O and the "connected" O

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> ans(0);
        for(int i=0;i<m;i++) {
            vector<bool> item(0);
            for(int j=0;j<n;j++) {
                item.push_back(false);
            }
            ans.push_back(item);
        }

        for(int i =0;i<m;i++) 
            for(int j=0;j<n;j++) 
                if (board[i][j] == 'O' && (i==0 || i == m-1 || j == 0 || j == n-1)) ans[i][j] = true;

        for(int i =0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if (ans[i][j]) {
                    if(i==0) {
                        dfs(ans, board, i+1,j, m,n);
                    }
                    if(i==m-1) {
                        dfs(ans, board, i-1,j, m,n);
                    }
                    if (j==0) {
                        dfs(ans, board, i,j+1, m,n);
                    }
                    if (j==n-1) {
                        dfs(ans, board, i,j-1, m,n);
                    }
                }
            }
        }
       
        for(int i=1;i<m-1;i++) {
            for(int j=1;j<n-1;j++) {
                char x = board[i][j];
                if (x=='O' && !ans[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }
    void dfs(vector<vector<bool>>& ans, vector<vector<char>>& board, int i, int j, int m,int n) {
        // cout << i << "====" << j << endl;
        if (i <= 0 || i >= m-1) return;
        if (j <= 0 || j >= n-1) return;
        if (board[i][j] == 'X') return;
        if (ans[i][j]) return;
        if (board[i][j] == 'O') {
            ans[i][j] = true;
        }
        dfs(ans, board, i-1,j,m,n);
        dfs(ans, board, i+1,j,m,n);
        dfs(ans, board, i,j-1,m,n);
        dfs(ans, board, i,j+1,m,n);
    }
};