How to find path matrix using bfs

Question

Supposing I have a matrix like:

where 0 means blank space, 1 is first item, 2 second item and 3 third item

0 0 0 0 0 
0 0 0 0 2
0 0 0 0 0
0 1 0 0 0
0 0 0 0 3

I start at (0,0) and would like to make a tour visiting 1,2,3 so in in terms of i,j it starts (0,0)->(3,1)->(1,4)->(4,4)

So To create a path I was thinking on

1. Run BFS from starting position (0,0) to 1 position (3,1)
2. Run BFS now starting position would be (3,1) to 2 (1,4)
3. Run BFS now starting position would be (1,4) to 3 (4,4)

TO use BFS we need Node definition and its child but how to do it? SO far I have:

using System;   
using System.IO;
using System.Collections.Generic;
using System.Text;
using System.Collections;


namespace ejercicio2
{

    class Program
    {
        struct position
        {
            public int row;
            public int col;
        };

        const int NOT_VISITED = 0;
        static int[,] map = {
                                {0, 0, 0, 0, 0}, 
                                {0, 0, 0, 0, 2},
                                {0, 0, 0, 0, 0},
                                {0, 1, 0, 0, 0},
                                {0, 0, 0, 0, 3}
                            };

        static void Main()
        {
            int who = 1;
            position start;
            start.row = 0;
            start.col = 0;
            //find 1
            bfs(start, map, who);
            start.row = 3;
            start.col = 1;
            //find 2
            who = 2;
            bfs(start, map,who);
            start.row = 1;
            start.col = 4;
            //find 3
             who = 3;
            bfs(start, map,who);

        }

        static void bfs(position present, int[,] map, int lookingfor)
        {
           //how to look for looking for??


        }
        private bool visited(int[,] board, position cell)
        {
            return board[cell.row, cell.col] < 1;
        }
    }
}

Answer 1

here code with full path

using System.IO;
using System;
using System.Collections.Generic;

class Program
{


       struct direction
            {
                public int x;
                public int y;
            };

            static direction[] directions = {
                                       new direction(){x = 1, y = 0},
                                       new direction(){x = 0, y = 1},
                                       new direction(){x = -1, y = 0},
                                       new direction(){x = 0, y = -1}
    };



     static int[,] visitedmap = resetVisitedMap();



         class Position
        {
            public int row;
            public int col;
            public Position  parent;
        };

        const int NOT_VISITED = 0;
        static int[,] map = {
                                {0, 4, 0, 0, 0}, 
                                {0, 0, 0, 0, 2},
                                {0, 0, 0, 0, 0},
                                {0, 1, 0, 0, 0},
                                {0, 0, 0, 0, 3}
                            };

        static void Main()
        {
            int[] who = new int[]{1,2,3,4};
            Position start = new Position();
            start.row = 0;
            start.col = 0;
            start.parent = null;
            Console.Write("("+start.row+","+start.col+")");
            //find 1
            foreach(int lookingfor in who){
                    start = bfs(start, map, lookingfor); 
                    Console.Write("->("+start.row+","+start.col+")");
            }

            Console.Write("\n Full path :\n");
            string path = "";
            while (start != null){
                path = "->("+ start.row+","+start.col+")"+path;
                start = start.parent;
            }
            Console.Write(path);
        }

        static Position bfs(Position present, int[,] map, int lookingfor)
        {
            Position[] poses = new Position[]{present};
            bool found = false;

           while (!found){
               foreach (Position pos in poses){
                   if (map[pos.row, pos.col] == lookingfor){
                      // Console.Write("------->Success at : ("+pos.row+","+pos.col+")");
                        visitedmap = resetVisitedMap();
                       return pos;
                   }
               }
            poses = cellsNear(poses);
           }

        return present;
        }

        static Position[] cellsNear(Position pos){
            //Console.WriteLine("Looking for cells near (" + pos.row +","+pos.col+")" );
            List<Position> result = new List<Position>();
            foreach (direction dir in directions){
                int rowCalculated = pos.row + dir.x;
                int colCalculated = pos.col + dir.y;
                if (rowCalculated >= 0 &&
                        colCalculated >= 0 &&
                        rowCalculated < map.GetLength(0) && 
                        colCalculated < map.GetLength(1) &&
                        !visited(rowCalculated,colCalculated)){
                    visitedmap[rowCalculated,colCalculated] = 1;
                    Position posPath = new Position();
                    posPath.col = colCalculated;
                    posPath.row = rowCalculated;
                    posPath.parent = pos;
                    result.Add(posPath);
                    //Console.WriteLine("found children cell : ("+rowCalculated+","+colCalculated+")" );
                }
            }
            //Console.WriteLine("\n");
            return result.ToArray();
        }

        static Position[] cellsNear(Position[] poses){
            List<Position> result = new List<Position>();
            foreach (Position pos in poses){
                result.AddRange(cellsNear(pos));
            }
            return result.ToArray();
        }

        static bool visited(int row, int col)
            {
                return visitedmap[row, col] == 1;
            }
    static int[,] resetVisitedMap(){
        return  new int[,]{
                                    {0, 0, 0, 0, 0}, 
                                    {0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0}
                                };
    }
}

as you can see it doesn't use Stack from Collections, but it use a kind of in memory stack, that make a cleaner solution for bfs problem, cause it simulate a tree

Answer 2

using System.IO;
using System;
using System.Collections.Generic;

class Program
{


       struct direction
            {
                public int x;
                public int y;
            };

            static direction[] directions = {
                                       new direction(){x = 1, y = 0},
                                       new direction(){x = 0, y = 1},
                                       new direction(){x = -1, y = 0},
                                       new direction(){x = 0, y = -1}
    };

     static int[,] visitedmap = resetVisitedMap();



               struct position
        {
            public int row;
            public int col;
        };

        const int NOT_VISITED = 0;
        static int[,] map = {
                                {0, 4, 0, 0, 0}, 
                                {0, 0, 0, 0, 2},
                                {0, 0, 0, 0, 0},
                                {0, 1, 0, 0, 0},
                                {0, 0, 0, 0, 3}
                            };

        static void Main()
        {
            int[] who = new int[]{1,2,3,4};
            position start;
            start.row = 0;
            start.col = 0;
            Console.Write("("+start.row+","+start.col+")");
            //find 1
            foreach(int lookingfor in who){
                    start = bfs(start, map, lookingfor); 
                    Console.Write("->("+start.row+","+start.col+")");
            }

        }

        static position bfs(position present, int[,] map, int lookingfor)
        {
            position[] poses = new position[]{present};
            bool found = false;

           while (!found){
               foreach (position pos in poses){
                   if (map[pos.row, pos.col] == lookingfor){
                      // Console.Write("------->Success at : ("+pos.row+","+pos.col+")");
                        visitedmap = resetVisitedMap();
                       return pos;
                   }
               }
            poses = cellsNear(poses);
           }

        return present;
        }

        static position[] cellsNear(position pos){
            //Console.WriteLine("Looking for cells near (" + pos.row +","+pos.col+")" );
            List<position> result = new List<position>();
            foreach (direction dir in directions){
                int rowCalculated = pos.row + dir.x;
                int colCalculated = pos.col + dir.y;
                if (rowCalculated >= 0 &&
                        colCalculated >= 0 &&
                        rowCalculated < map.GetLength(0) && 
                        colCalculated < map.GetLength(1) &&
                        !visited(rowCalculated,colCalculated)){
                    visitedmap[rowCalculated,colCalculated] = 1;
                    result.Add(new position(){row =rowCalculated, col = colCalculated });
                    //Console.WriteLine("found children cell : ("+rowCalculated+","+colCalculated+")" );
                }
            }
            //Console.WriteLine("\n");
            return result.ToArray();
        }

        static position[] cellsNear(position[] poses){
            List<position> result = new List<position>();
            foreach (position pos in poses){
                result.AddRange(cellsNear(pos));
            }
            return result.ToArray();
        }

        static bool visited(int row, int col)
            {
                return visitedmap[row, col] == 1;
            }
    static int[,] resetVisitedMap(){
        return  new int[,]{
                                    {0, 0, 0, 0, 0}, 
                                    {0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0}
                                };
    }
}

just uncomment lines with logging to see how search is performed.... if you'll have question, feel free to ask..