class AllShorestPaths
    {
        static string[,] matrix={
                                    {"0","0","0","X ","0","0","X ","X "},
                                    {"X ","0","0","X ","0","0","0","X "},
                                    {"0","0","0","0","X ","0","X ","X "},
                                    {"X ","0","0","X ","0","0","0","0"},
                                    {"0","0","X ","0","0","0","X ","X "},
                                    {"X ","0","0","0","X ","0","0","X "}
                                };
        class Node
        {
            private int row;
            private int col;
            private int depth;

            public int Row
            {
                get
                {
                    return this.row;
                }

                set
                {
                    if (value >= 0)
                        this.row = value;

                    else
                    {
                        throw new ArgumentException("Row can not be negative!");
                    }
                }
            }

            public int Col
            {
                get
                {
                    return this.col;
                }

                set
                {
                    if (value >= 0)
                        this.col = value;

                    else
                    {
                        throw new ArgumentException("Row can not be negative!");
                    }
                }
            }

            public int Depth
            {
                get
                {
                    return this.depth ;
                }

                set
                {
                    this .depth =value ;
                }
            }

            public Node(int row, int col, int depth)
            {
                this.Row = row;
                this.Col = col;
                this.Depth = depth;
            }
        }

        static bool IsInRange(int row, int col)
        {
            if (row < 0 || row >= matrix.GetLength(0) || col < 0 || col >= matrix.GetLength(1))
                return false ;
            return true;
        }

        static void FindShortestPathsBFS(int startRow, int startCol)
        {
            matrix[startRow, startCol] = "* ";
            bool[,] visited = new bool[matrix.GetLength(0), matrix.GetLength(1)];
            Queue<Node> q = new Queue<Node>();
            q.Enqueue (new Node (startRow ,startCol ,0));
            visited [startRow ,startCol ]=true;

            while (q.Count > 0)
            {
                Node current = q.Dequeue();
                int row = current.Row;
                int col = current.Col;
                visited[row, col] = true;

                if (!(row == startRow && col == startCol))
                {
                    matrix[row, col] = current.Depth+ " ";
                }

                if (IsInRange(row + 1, col) && matrix[row + 1, col] == "0" && !visited[row+1, col])
                {
                    q.Enqueue (new Node (row +1,col,current .Depth +1));
                }

                if (IsInRange(row - 1, col) && matrix[row - 1, col] == "0" && !visited[row - 1, col])
                {
                    q.Enqueue(new Node(row - 1, col,current .Depth +1));
                }

                if (IsInRange(row , col+1) && matrix[row , col+1] == "0" && !visited[row , col+1])
                {
                    q.Enqueue(new Node(row , col+1, current.Depth + 1));
                }

                if (IsInRange(row , col-1) && matrix[row , col-1] == "0" && !visited[row, col-1])
                {
                    q.Enqueue(new Node(row , col-1, current.Depth + 1));
                }
            }
            FillUnreachable();
            PrintMatrix();
        }

        static void FillUnreachable()
        {
            for (int row = 0; row < matrix.GetLength(0); row++)
            {
                for (int col = 0; col < matrix.GetLength(1); col++)
                {
                    if (matrix[row, col] == "0")
                        matrix[row, col] = "u";
                }
            }
        }

        static void PrintMatrix()
        {
            for (int row = 0; row < matrix.GetLength(0); row++)
            {
                for (int col = 0; col < matrix.GetLength(1); col++)
                {
                    Console.Write("{0,5}",matrix[row, col]);
                }
                Console.WriteLine();
            }

        }

        static void Main(string[] args)
        {
            FindShortestPathsBFS(0,0);
        }
    }