using System; 

using System.Collections.Generic; 

public class Program  

{ 

    static int ROW; 

    static int COL; 

​

    public class Point 

    { 

        public int x; 

        public int y; 

​

        public Point(int x, int y) 

        { 

            this.x = x; 

            this.y = y; 

        } 

    }; 

​

    public class queueNode 

    { 

        public Point pt;  

​

        public int dist;  

​

        public queueNode(Point pt, int dist) 

        { 

            this.pt = pt; 

            this.dist = dist; 

        } 

    }; 

​

    static bool isValid(int row, int col) 

    { 

        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL); 

    } 

​

    static int []rowNum = {-1, 0, 0, 1}; 

    static int []colNum = {0, -1, 1, 0}; 

​

    static int BFS(int [,]mat, Point src, Point dest) 

    { 

        if (mat[src.x, src.y] != 1 ||  mat[dest.x, dest.y] != 1) 

            return -1; 

​

        bool [,]visited = new bool[ROW, COL]; 

​

        visited[src.x, src.y] = true; 

​

        Queue<queueNode> q = new Queue<queueNode>(); 

​

        queueNode s = new queueNode(src, 0); 

        q.Enqueue(s); 

​

        while (q.Count != 0) 

        { 

            queueNode curr = q.Peek(); 

            Point pt = curr.pt; 

​

            if (pt.x == dest.x && pt.y == dest.y) 

                return curr.dist; 

​

            q.Dequeue(); 

​

            for (int i = 0; i < 4; i++) 

            { 

                int row = pt.x + rowNum[i]; 

                int col = pt.y + colNum[i]; 

​

                if (isValid(row, col) &&  mat[row, col] == 1 &&  !visited[row, col]) 

                { 

                    // mark cell as visited and enqueue it 

                    visited[row, col] = true; 

                    queueNode Adjcell = new queueNode(new Point(row, col), curr.dist + 1 ); 

                    q.Enqueue(Adjcell); 

                } 

            } 

        } 

​

        return -1; 

    } 

​

    // Driver Code 

    public static void Main(String[] args)  

    { 

        int x, bob_x, bob_y, src_x = 0, src_y = 0, shrt_path = 0;

        Console.Write("Enter Number of Rows: ");

        ROW = int.Parse(Console.ReadLine());

        Console.Write("Enter Number of Columns: ");

        COL = int.Parse(Console.ReadLine());

        int[,] arr= new int[ROW,COL];

        int[,] arr2= new int[ROW,COL];

        for(int i = 0; i < ROW; i++){

            for(int j = 0; j < COL; j++){

                Console.Write("Enter Value: ");

                x = int.Parse(Console.ReadLine());

                if(x == 1){

                    arr2[i,j] = 0;

                }

                if(x == 2 || x == 0){

                    arr2[i,j] = 1;

                }

                arr[i,j] = x;

            }

        }

        Console.Write("Enter X Value of Bob: ");

        bob_x = int.Parse(Console.ReadLine());

        Console.Write("Enter Y value of Bob: ");

        bob_y = int.Parse(Console.ReadLine());

        List<List<int>> lst = new List<List<int>>();

        for(int i=0; i < ROW; i++){

            for(int j=0; j < COL; j++){

                if(arr[i,j] == 2){

                    List<int> temp = new List<int>();

                    temp.Add(i);

                    temp.Add(j);

                    lst.Add(temp);

                }

            }

        }

        /**for(int i = 0; i < lst.Count; i++){

            foreach(var j in lst[i]){

                Console.Write(j);

            }

            Console.WriteLine();

        }

        for(int i = 0; i < ROW; i++){

            for(int j = 0; j < COL; j++){

                Console.Write(arr2[i,j]);

            }

            Console.WriteLine();

        }**/

        for(int i = 0; i < lst.Count; i++){

            Point source = new Point(src_x, src_y); 

            src_x = lst[i][0];

            src_y = lst[i][1];

            Point dest = new Point(lst[i][0], lst[i][1]); 

​

            int dist = BFS(arr2, source, dest);

            if (dist != int.MaxValue) 

                shrt_path += dist;

            else

                break;

        }

​

        Point source2 = new Point(src_x, src_y); 

        Point dest2 = new Point(bob_x, bob_y); 

​

        int dist2 = BFS(arr2, source2, dest2); 

​

        if (dist2 != int.MaxValue){

            shrt_path += dist2;

            Console.WriteLine("Shortest Path is " + shrt_path);

        }

        else{

            Console.WriteLine("Shortest Path doesn't exist");

        }

    } 

}