DFS based solution O(m*n) space and time.


  • 0
    A

    Simple DFS solution to avoid recursive stack overflow:

    class Solution {
        bool isEdge(int i, int j, int m, int n)
        {
            if(i == m-1 || i == 0)  return true;
            if(j == n-1 || j == 0) return true;
            
            return false;
        }
        
    public:
        void solve(vector<vector<char>>& board) {
            int m = board.size();
            if(m <= 1) return;
            int n = board[0].size();
            
            vector<vector<bool>> visited(m, vector<bool>(n, false));
            
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if(visited[i][j]) continue;
                    
                    if(board[i][j] == 'X')
                    {
                        visited[i][j] = true;
                        continue;
                    }
    
                    bool reach = false;
                    vector<pair<int,int>> all;
                    
                    queue<pair<int,int>> dfs;
                    dfs.push(make_pair(i,j));
                    
                    while(!dfs.empty())
                    {
                        pair<int,int> f = dfs.front();
                        dfs.pop();
                        
                        if(f.first >= m || f.first < 0) continue;
                        if(f.second >= n || f.second < 0) continue;
                        if(visited[f.first][f.second]) continue;
                        if(board[f.first][f.second] == 'X') continue;
                        
                        all.emplace_back(f);
                        if(isEdge(f.first,f.second, m, n)) reach = true;
                        visited[f.first][f.second] = true;
                        
                        dfs.push(make_pair(f.first-1, f.second));
                        dfs.push(make_pair(f.first+1, f.second));
                        dfs.push(make_pair(f.first, f.second+1));
                        dfs.push(make_pair(f.first, f.second-1)); 
                    }
                    
                    if(!reach)
                    {
                        for(int k = 0; k < all.size(); k++)
                        {
                            board[all[k].first][all[k].second] = 'X';
                        }
                    }
                }
            }
            
            return;
        }
    };
    

Log in to reply
 

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