C# - remove edge regions then 1 pass to finish. DFS or BFS?


  • 0

    I see that using a BFS instead of DFS is recommended. Is that because BFS will queue up fewer cells then the DFS stack? Can you explain why it will work this way? Wouldn't it depend on the shape of the region? Perhaps it has to do with the queue avoiding the worst case scenario better than then the stack?

    Here I use DFS using a stack instead of recursion.

        public void Solve(char[,] board) 
        {
            int rows = board.GetLength(0);
            int cols = board.GetLength(1);
            char EDGE_MARKER = '#';
            
            // remove from consideration any cells connected to the edges
            MarkEdgeRegions(board, rows, cols, EDGE_MARKER);
            
            // now mark off everything else and reverse the marked edges
            for (int r = 0; r < rows; r++)
            {
                for (int c = 0; c < cols; c++)
                {
                    if (board[r,c] == 'O') board[r,c] = 'X';
                    if (board[r,c] == EDGE_MARKER) board[r,c] = 'O';
                }
            }
        }
        
        public void MarkEdgeRegions(char[,] board, int rows, int cols, char EDGE_MARKER)
        {
            // will Push row index then col index, need to Pop in reverse
            Stack<int> stack = new Stack<int>();
            
            // look for cells along TOP and BOTTOM edges
            for (int c = 0; c < cols; c++)
            {
                if (board[0,c] == 'O') // top
                { 
                    stack.Push(0);
                    stack.Push(c);
                    board[0,c] = EDGE_MARKER;
                }            
                if (board[rows-1,c] == 'O') // bottom
                { 
                    stack.Push(rows-1);
                    stack.Push(c);
                    board[rows-1,c] = EDGE_MARKER;
                }
            }
            
            // look for cells along LEFT and RIGHT edges (corners already processed)
            for (int r = 1; r < rows - 1; r++)
            {
                if (board[r,0] == 'O') // left
                { 
                    stack.Push(r);
                    stack.Push(0);
                    board[r,0] = EDGE_MARKER;
                }            
                if (board[r,cols-1] == 'O') // right
                { 
                    stack.Push(r);
                    stack.Push(cols-1);
                    board[r,cols-1] = EDGE_MARKER;
                }
            }
            
            // now crawl to mark off all connected cells
            while (stack.Count > 0)
            {
                int c = stack.Pop();
                int r = stack.Pop();
                
                // look above
                if (r > 0 && board[r-1,c] == 'O')
                {
                    stack.Push(r-1);
                    stack.Push(c);
                    board[r-1,c] = EDGE_MARKER;
                }
                
                // look below
                if (r < rows - 1 && board[r+1,c] == 'O')
                {
                    stack.Push(r+1);
                    stack.Push(c);
                    board[r+1,c] = EDGE_MARKER;
                }
                
                // look left
                if (c > 0 && board[r,c-1] == 'O')
                {
                    stack.Push(r);
                    stack.Push(c-1);
                    board[r,c-1] = EDGE_MARKER;
                }
                
                // look right
                if (c < cols - 1 && board[r,c+1] == 'O')
                {
                    stack.Push(r);
                    stack.Push(c+1);
                    board[r,c+1] = EDGE_MARKER;
                }
            }
        }
    

Log in to reply
 

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