广度优先搜索Java中的8x8网格-Java 学习之路

我要做的是计算使用最短路径到达目标需要多少动作 . 必须使用广度优先搜索来完成 . 我将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;
}

2 回答

0
您需要在队列中存储2件事 . 让我们将队列中的每个项目称为一个节点 .
- 位置（您已存储）
- count（从起始位置到达此位置所需的移动）
首先将起始位置的计数分配给0 .

算法的工作方式是：
- 您从队列中弹出一个节点
- 您可以确定从刚刚弹出的节点指定的位置开始的位置 . 也就是说，如果将其视为"making a tree on the fly"，则确定从队列中弹出的节点的子节点
- 您将这些子项添加到队列中 .
在第3步中，将节点子节点添加到队列时，您必须确定需要添加到此节点的计数 . 这个数字简直就是 count of the parent node (that you popped in step 1) + 1

最后，您的返回值将是与承载目标位置的节点关联的计数 .

例如，让我们使用4x4网格，其中position [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 .

Edit

如果要获取从源到目标的路径，则当前编码不会按原样运行 . 您需要使用计数维护一个大小为8x8的单独2D数组，而不是在节点本身中对它们进行编码 . 当您最终找到目的地的计数时，您使用2D计数阵列从目的地回溯到源 . 基本上，如果你可以通过9次移动到达目的地，你可以通过8次移动到达其中一个相邻位置 . 因此，您会找到计数为8且与目的地相邻的位置 . 你迭代地重复这个，直到你到达源头 .

您描述的方法，其中您向节点添加额外元素不起作用 . 我会留给你找出原因，因为这是作业:)
回复于 2024-05-09T19:22:19+08:00

这是你的代码的一个很好的 short alternative . 完全相同的想法，但不需要这么多'if'条件，您检查每个坐标的有效性 . 这一切都可以一次完成 . 看一看 .

我尽可能多地评论了这个解释 . 即使对于那些没有任何想法的人来说，它也是可读的 . 当我为一个类似的（相同的？）问题实施一个解决方案时，我碰巧碰到了你的问题，一个困在迷宫中的家伙必须找到出路 . 网格中有陷阱（B）和可移动区域（E） . 目标是到达目的地（G） .

无论如何，这是通用代码 . 我接受了行，列，然后是完整的网格 . 我只是打印是否有可能到达目的地 . 我将其余部分留给那些正在阅读这个练习的人，以确保你理解代码;）

请注意 main objective 我的答案是向您展示 size of your BFS function could be reduced . 我发布我的整个解决方案只是为了让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

回复于 2024-05-09T19:22:19+08:00

广度优先搜索Java中的8x8网格

2 回答

相关问题