java - Java 8x8网格上的广度优先搜索

我想做的是计算使用最短路径到达目标所需的移动次数。必须使用广度优先搜索来完成。我将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。

该算法的工作方式是:

您从队列

中弹出一个节点

可确定您可以从刚刚弹出的节点指定的位置到达哪里。也就是说，如果您将其视为“动态生成树”，那么您将确定从队列

中弹出的节点的子节点

，您可以将这些子级添加到队列中。

在第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数组，而不是在节点本身中对其进行编码。当您最终找到目标的计数时，您将使用2D计数数组将其从目标回溯到源。本质上，如果您能以9个 Action 到达目的地，则可以以8个 Action 到达其相邻位置之一。因此，您找到了计数为8且与目的地相邻的位置。您反复重复此过程，直到获得源代码为止。

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