0

假设我有一个像这样的矩阵：

其中 0 表示空格，1 表示第一项，2 第二项和 3 第三项

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

我开始(0,0)并想进行一次巡回演出，1,2,3因此i,j就开始了(0,0)->(3,1)->(1,4)->(4,4)

所以要创造一条我正在考虑的道路

  1. 从起始位置 (0,0) 运行 BFS 到 1 位置 (3,1)
  2. 现在运行 BFS，起始位置将从 (3,1) 到 2 (1,4)
  3. 现在运行 BFS，起始位置为 (1,4) 到 3 (4,4)

要使用 BFS，我们需要节点定义和它的子节点，但是怎么做呢？到目前为止，我有：

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;
        }
    }
}
4

2 回答 2

1

这里有完整路径的代码

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}
                                };
    }
}

如您所见，它不使用 Collections 中的 Stack，但它使用一种内存堆栈，这为 bfs 问题提供了更简洁的解决方案，因为它模拟了一棵树

于 2013-09-19T18:20:22.923 回答
1 
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}
                                };
    }
}

只需取消注释行以查看如何执行搜索.. 如果您有问题，请随时提问..

于 2013-09-19T14:25:14.623 回答