10

我要做的是计算使用最短路径到达目标所需的移动次数。必须使用广度优先搜索来完成。我将 8x8 网格放入一个 2d 数组中，该数组用四个字符之一填充，E 表示空（可以移动到这些位置），B 表示阻塞（不能在此处移动），R 表示机器人（起点）或 G为目标。该算法必须按向上、向左、向右、向下的顺序检查可移动空间，我相信我做得对。检查节点后，它将其内容更改为“B”。如果无法达到目标，则应返回 0。

我已经更改了我的代码以实现 Kshitij 告诉我的内容，并且效果很好。我太累了，看不到在每个新数据集后我都没有初始化队列，哈哈。谢谢您的帮助！

public static int bfSearch(){
    Queue <int []> queue = new LinkedList <int []> ();
    int [] start = {roboty,robotx,0};
    queue.add(start);

    while (queue.peek() != null){
        int [] array = queue.remove();

            if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){

                if (grid[array[0]-1][array[1]] == 'G'){
                    return array[2]+1; 
                }
                else{
                    grid[array[0]-1][array[1]] = 'B';
                    int [] temp = {array[0]-1, array[1], array[2]+1};
                    queue.add(temp);
                }
            }

            if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){

                if (grid[array[0]][array[1]-1] == 'G'){
                    return array[2]+1;
                }
                else{
                    grid[array[0]][array[1]-1] = 'B';
                    int [] temp = {array[0], array[1]-1, array[2]+1};
                    queue.add(temp);
                }
            }

            if(array[1]+1 <= 7 && grid[array[0]][array[1]+1] != 'B'){

                if (grid[array[0]][array[1]+1] == 'G'){
                    return array[2]+1;
                }
                else{
                    grid[array[0]][array[1]+1] = 'B';
                    int [] temp = {array[0], array[1]+1, array[2]+1};
                    queue.add(temp);
                }
            }

            if(array[0]+1 <= 7 && grid[array[0]+1][array[1]] != 'B'){

                if (grid[array[0]+1][array[1]] == 'G'){
                    return array[2]+1;
                }
                else{
                    grid[array[0]+1][array[1]] = 'B';
                    int [] temp = {array[0]+1, array[1], array[2]+1};
                    queue.add(temp);
                }
            }
        }           
    return 0;
}
4

2 回答 2

16

您需要在队列中存储 2 件东西。让我们将队列中的每个项目称为节点。

  1. 位置（您已经存储）
  2. 计数（从起始位置到该位置所需的移动）

您首先将起始位置的计数分配为 0。

该算法的工作方式是：

  1. 你从队列中弹出一个节点
  2. 你确定你可以从你刚刚弹出的节点指定的位置去哪里。也就是说，如果您将此视为“即时制作树”，则您正在确定从队列中弹出的节点的子节点
  3. 您将这些孩子添加到队列中。

在第三步中，当您将节点子节点添加到队列中时，您必须确定需要添加到该节点的计数。这个计数简直就是count of the parent node (that you popped in step 1) + 1

最后，您的返回值将是与携带目标位置的节点关联的计数。

例如，让我们使用 4x4 网格，其中位置 [0,0] 是起点，位置 [0,3] 是目的地。

S E E B
E B E E
B B B E
G E E E

最初，您的队列将是：

[{(0, 0), 0}]

其中，里面的值()是位置，里面的第二个值{}是计数。

您从队列中弹出此节点，并确定您可以到达位置 (0,1) 和 (1,0)。因此，您将项目添加{(0, 1), 1}到{(1, 0), 1}队列中。请注意，计数为 1，因为弹出节点的计数为 0，我们将其增加 1。您的队列现在看起来像：

[{(0, 1), 1},  {(1, 0), 1}]

你弹出第一个元素，意识到它没有可行的孩子，所以你继续前进。

您弹出剩余的元素，并发现它在位置 (2, 0) 处为您提供了一个您可以到达的节点。由于您弹出的节点的计数为 1，因此您将这个与 count = 1 + 1 = 2 配对的新位置添加到队列中。

最终，您将从队列中弹出目标节点，其计数为 9。

编辑

如果您想获取从源到目的地的路径，当前编码不能按原样工作。您需要使用计数维护一个单独的大小为 8x8 的二维数组，而不是在节点本身中对它们进行编码。当您最终找到目的地的计数时，您使用 2D 计数数组从目的地回溯到源。本质上，如果您可以在 9 步内到达目的地，那么您可以在 8 步内到达其相邻位置之一。因此，您找到计数为 8 且与目的地相邻的位置。您反复重复此操作，直到找到源。

您描述的向节点添加额外元素的方法不起作用。我会把它留给你找出原因，因为这是家庭作业:)

于 2012-04-11T03:24:52.573 回答
0

这是您的代码的一个不错的简短替代方案。完全相同的想法，但不需要那么多“如果”条件来检查每个坐标的有效性。这一切都可以一口气完成。看一看。

我已经尽可能多地评论了解释。即使对于没有丝毫想法的人来说，它也可以阅读。当我为类似（相同？）问题实施解决方案时，我碰巧遇到了您的问题，其中一个被困在迷宫中的人必须找到出路。网格中有陷阱（B）和可移动区域（E）。目标是到达他的目的地（G）。

无论如何，这是通用代码。我接受行数，列数，然后是完整的网格。我只打印是否可以到达目的地。我把剩下的留给阅读这篇文章的人作为练习，以确保你已经理解了代码；）

请注意，我回答的主要目的是向您展示BFS 函数的大小可以减小。我发布我的整个解决方案只是为了给出在网格中应用 BFS 的总体思路，因为我在学习它时遇到了困难。希望这将帮助陷入相同情况的人。如果您想要该职位或所遵循的路径或任何其他内容，请按照此问题答案中的说明进行操作。自己做 ;）

import java.util.*;

/**
 * Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA
 */

class MAZE
{
    static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates
    static int[] dx={1,-1,0,0};//right, left, NA, NA
    static int[] dy={0,0,1,-1};//NA, NA, bottom, top
    static char[][] grid;//Main grid
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);//I suggest using faster IO if you have performance concerns. I did. Scanner is readable hence the choice
        r=sc.nextInt();
        c=sc.nextInt();
        grid=new char[r][c];
        for(int i=0;i<r;i++)
        {
            char[] s1=sc.next().toCharArray();//Reading a line of the Grid
            System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually
        }
        s1=sc.nextInt()-1;
        s2=sc.nextInt()-1;
        f1=sc.nextInt()-1;
        f2=sc.nextInt()-1;
        if(MAZEBFS())
        {
            System.out.println("PATH EXISTS");
        }
        else
        {
            System.out.println("PATH DOES NOT EXIST");
        }
    }
    private static boolean MAZEBFS()
    {
        if(s1==f1&&s2==f2)
        {
            return true;//He's already there
        }
        else
        {
            grid [f1][f2]='G';//finish
            Queue<int[]> q=new LinkedList<int[]>();
            int[]start={s1,s2};//Start Coordinates
            q.add(start);//Adding start to the queue since we're already visiting it
            grid[s1][s2]='B';
            while(q.peek()!=null)
            {
                int[]curr=q.poll();//poll or remove. Same thing
                for(int i=0;i<4;i++)//for each direction
                {
                    if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c))
                    {
                        //Checked if x and y are correct. ALL IN 1 GO
                        int xc=curr[0]+dx[i];//Setting current x coordinate
                        int yc=curr[1]+dy[i];//Setting current y coordinate
                        if(grid[xc][yc]=='G')//Destination found
                        {
                            //System.out.println(xc+" "+yc);
                            return true;
                        }
                        else if(grid[xc][yc]=='E')//Movable. Can't return here again so setting it to 'B' now
                        {
                            //System.out.println(xc+" "+yc);
                            grid[xc][yc]='B';//now BLOCKED
                            int[]temp={xc,yc};
                            q.add(temp);//Adding current coordinates to the queue
                        }
                    }
                }
            }
            return false;//Will return false if no route possible
        }
    }
}

实际代码：http: //ideone.com/jiZKzn

欢迎提出任何建议。干杯：D

于 2015-05-01T12:18:53.457 回答