我想做的是计算使用最短路径到达目标需要多少步。它必须使用广度优先搜索来完成。我将 8x8 网格放入一个二维数组中，其中填充了四个字符之一，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。
算法的工作方式是:
- 你从队列中弹出一个节点
- 你决定你可以从你刚刚弹出的节点指定的位置去哪里。也就是说，如果您将此视为“即时生成树”，您就是在确定从队列中弹出的节点的子节点
- 您将这些 child 添加到队列中。
在您的第 3 步中，当您将节点子节点添加到队列时，您必须确定需要添加到该节点的计数。这个计数就是 父节点的计数(您在第 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}]
你弹出第一个元素，意识到它没有可行的 child ，所以你继续。
您弹出剩余的元素，并发现它在位置 (2, 0) 处为您提供了一个您可以到达的节点。由于您弹出的节点计数为 1，因此您将这个与计数 = 1 + 1 = 2 配对的新位置添加到队列中。
最终，您将从队列中弹出目标节点，它的计数将为 9。
编辑
如果你想得到从源到目的地的路径，当前的编码不能按原样工作。您需要使用计数维护一个大小为 8x8 的单独二维数组，而不是在节点本身中对它们进行编码。当您最终找到目的地的计数时，您可以使用二维计数数组从目的地回溯到源。本质上，如果您可以在 9 步内到达目的地，则可以在 8 步内到达其相邻位置之一。因此，您找到计数为 8 且与目的地相邻的位置。您反复重复此操作，直到到达源头。
您描述的向节点添加额外元素的方法不起作用。我会留给你找出原因，因为这是家庭作业:)
关于java - Java 中 8x8 网格的广度优先搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10099221/