Simple and clean solution


  • 1
    N

    Say the 2D board is m, n array. We can get this conclusion: only region with any 'O' node on the border are not surrounded by 'X'. Those nodes are (0, 0 to n), (m-1, 0 to n), (0 to m, 0), (0 to m, n-1).
    So, the solution is go through all border nodes with value 'O'. traverse the region and mark them in shadow array d. mark all other 'O' nodes without this mark to 'X'. Complexity is time O(n), space O(n). worst case for time is traverse all nodes twice.

    class Solution {
        public:
            void solve(vector<vector<char>> &board) {
        	int m = board.size(); if (!m) return;
        	int n = board[0].size(); if (!n) return;
        
        	// Create 2D data for the board,  1: connected with 'O' nodes on the border
        	vector<vector<int>> d(m,vector<int>(n, -1));
        	
        	// Find the region connected to the 'O' nodes on the borders, otherwise, the rest nodes with 'O' are surrounded by 'x'
        	for(int j=0;j<n;j++)
        		if((board[0][j]=='O') && (d[0][j]==-1))
        			traverseRegion(0,j,m,n,board,d);
        
        	for(int j=0;j<n;j++)
        		if((board[m-1][j]=='O') && (d[m-1][j]==-1))
        			traverseRegion(m-1,j,m,n,board,d);
        
        	for(int i=1;i<m-1;i++)
        		if((board[i][0]=='O') && (d[i][0]==-1))
        			traverseRegion(i,0,m,n,board,d);
        
        	for(int i=1;i<m-1;i++)
        		if((board[i][n-1]=='O') && (d[i][n-1]==-1))
        			traverseRegion(i,n-1,m,n,board,d);
        
        	// mark all 'O' nodes to 'X' unless they are connected to 'O' nodes on the border
        	for(int i=0;i<m;i++)
        	{
        		for(int j=0;j<n;j++)
        		{
        			if ((board[i][j] == 'O') && (d[i][j]==-1))
        				board[i][j] = 'X';
        		}
        	}
            }
        
        protected:
        	void traverseRegion(int i, int j, int m, int n, vector<vector<char>> &board, vector<vector<int>>& d)
        	{
        		d[i][j] = 1;
        		if (i>0 && board[i-1][j] == 'O' && d[i-1][j]==-1)
        			traverseRegion(i-1,j,m,n,board,d);
        		if (i<m-1 && board[i+1][j] == 'O' && d[i+1][j]==-1)
        			traverseRegion(i+1,j,m,n,board,d);
        
        		if (j>0 && board[i][j-1] == 'O' && d[i][j-1]==-1)
        			traverseRegion(i,j-1,m,n,board,d);
        		if (j<n-1 && board[i][j+1] == 'O' && d[i][j+1]==-1)
        			traverseRegion(i,j+1,m,n,board,d);
        	}
        };

  • -1
    G

    It is my solution. I change the char 'O' to '.' to mark it and then change it back in the second traversal.

    class Solution {
    public:
    	void solve(vector<vector<char>> &board) {
    		m = board.size();
    		if (m <= 2) return;
    		n = board[0].size();
    		if (n <= 2) return;
    
    		for (int x = 0; x < n; ++x)
    		{
    			dfs(board, x, 0);
    			dfs(board, x, m - 1);
    		}
    		for (int y = 0; y < m; ++y)
    		{
    			dfs(board, 0, y);
    			dfs(board, n - 1, y);
    		}
    
    		for (int y = 0; y < m; ++y)
    		{
    			for (int x = 0; x < n; ++x)
    			{
    				if (board[y][x] == 'O') board[y][x] = 'X';
    				else if (board[y][x] == '.') board[y][x] = 'O';
    			}
    		}
    
    	}
    private:
    	void dfs(vector<vector<char>> &board, int x, int y)
    	{
    		if (board[y][x] != 'O') return;
    		board[y][x] = '.';
    		if (x > 0) dfs(board, x - 1, y);
    		if (x < n - 1) dfs(board, x + 1, y);
    		if (y > 0) dfs(board, x, y - 1);
    		if (y < m - 1) dfs(board, x, y + 1);
    	}
    	int m, n;
    };

  • 0
    L

    did you get memory limit exceeded? I allocated a queue for BFS, which in theory requires less memory than your solution, but I got memory limit.


  • 0
    N

    no, i didn't


  • 0
    B

    will this program cause stack overflow? I have checked my code(which is writen in C,after reading your code) many times,always got runtime error when the numRows&&numColumns become big. it works with small numRows&&numColumns. I'm almost quite sure it's resulted from two many recursions. Please help me.


  • 0
    Y

    It will cause runtime error


Log in to reply
 

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