C# BFS use stack to avoid recursion


  • 0
    M
     public class Solution
            {
                public void Solve(char[,] board)
                {
                    int n = board.GetLength(0);
                    int m = board.GetLength(1);
                    bool[,] flag = new bool[n, m];
                    Func<int, int, bool> IsEdge = (i, j) =>
                    {
                        return i == 0 || j == 0 || i == n-1 || j == m-1;
                    };
                    Func<int, int, bool> CheckLocation = (i, j) =>
                    {
                        if (i >= 0 && i < n && j >= 0 && j < m)
                        {
                            if (board[i, j] == 'O' && !flag[i, j])
                                return true;
                        }
                        return false;
                    };
                    for (int i = 0; i < n; i++)
                        for (int j = 0; j < m; j++)
                        {
                            if (!flag[i, j])
                                if (board[i, j] == 'O' && IsEdge(i, j))
                                {
                                    Stack<int> stacki = new Stack<int>();
                                    Stack<int> stackj = new Stack<int>();
                                    stacki.Push(i);
                                    stackj.Push(j);
                                    while (stackj.Count > 0)
                                    {
                                        int row = stacki.Pop();
                                        int col = stackj.Pop();
                                        flag[row, col] = true;
                                        if (CheckLocation(row, col + 1))
                                        {
                                            stacki.Push(row);
                                            stackj.Push(col + 1);
                                        }
                                        if (CheckLocation(row, col - 1))
                                        {
                                            stacki.Push(row);
                                            stackj.Push(col - 1);
                                        }
                                        if (CheckLocation(row + 1, col))
                                        {
                                            stacki.Push(row + 1);
                                            stackj.Push(col);
                                        }
                                        if (CheckLocation(row - 1, col))
                                        {
                                            stacki.Push(row - 1);
                                            stackj.Push(col);
                                        }
                                    }
                                }
                        }
                    for (int i = 1; i < n; i++)
                        for (int j = 1; j < m; j++)
                        {
                            if (board[i, j] == 'O' && !flag[i, j])
                                board[i, j] = 'X';
                        }
                }
            }
    

Log in to reply
 

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