Why tle? time O(mn), space O(mn)


  • 0
    R
    class Solution {
    public:
        int m, n;
        int di[4]={-1,1,0,0}, dj[4]={0,0,-1,1};
        vector<vector<char>> b;
        vector<vector<bool>> v;
        bool outrange(int i, int j){
            return i<0 || i>=m || j<0 || j>=n;
        }
        void dfs(int nowi, int nowj){
            if(outrange(nowi, nowj) || v[nowi][nowj] || b[nowi][nowj]=='X') return ;
            v[nowi][nowj]=1;
            for(int k=0;k<4;k++){
                int ni=nowi+di[k], nj=nowj+dj[k];
                dfs(ni, nj);
            }
        }
        void solve(vector<vector<char>>& b_) {
            b=b_;
            m = b.size(), n= m ? b[0].size() : 0;
            v.assign(m, vector<bool>(n, false));
            for(int i=0;i<m;i++){
                if(v[i][0] || b[i][0]=='X') continue;
                dfs(i, 0);
            }
            for(int i=0;i<m;i++){
                if(v[i][n-1] || b[i][n-1]=='X') continue;
                dfs(i, n-1);
            }
            for(int j=0;j<n;j++){
                if(v[0][j] || b[0][j]=='X') continue;
                dfs(0, j);
            }
            for(int j=0;j<n;j++){
                if(v[m-1][j] || b[m-1][j]=='X') continue;
                dfs(m-1, j);
            }
            for(int i=1;i<m-1;i++){
                for(int j=1;j<n-1;j++){
                    if(!v[i][i] && b[i][j]=='O'){
                        b[i][j]='X';
                    }
                }
            }
            b_=b;
        }
    };

Log in to reply
 

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