c++ - 使用数组的广度优先搜索

Question

我正在尝试使用数组对迷宫实现广度优先搜索。我现在面临的问题是我不能同时扩展路径。像这样:

#######
123456#
#3###7#
#4###8#
#5###9G
#######

我现在使用的方法是使用 for 循环遍历数组。我将起点设置为 C(当前)，将终点设置为 G(目标)。 当我遍历迷宫时，我搜索存储字符“C”的数组位置。然后我检查了上、下、左、右是否是一堵墙。如果没有，我将移至下一个括号。新括号我将其设置为“C”，而前一个括号我将其设置为“O”。

for (int i = 1; i < 12; i++)
    {
        for (int j = 0; j < 12; j++)
        {
            // find current node
            if (maze[i][j] == 'C')
            {

            if (maze[i][j-1] == ' ')       // up
                {
                    maze[i][j-1] = 'C';
                    maze[i][j] = 'O';
                }

                else if (maze[i][j+1] == ' ')       // down
                {
                    maze[i][j+1] = 'C';
                    maze[i][j] = 'O';
                }

                else if (maze[i-1][j] == ' ')       // left
                {
                    maze[i-1][j] = 'C';
                    maze[i][j] = 'O';
                }
                else if (maze[i+1][j] == ' ')
                {
                    maze[i+1][j] = 'C';
                    maze[i][j] = 'O';  

                  }
    }

“C”括号在交界处的部分如何实现？我使用了一个 for 循环，所以它一直像这样出现:

#######   #######   #######   #######  #######  #######  #######  #######
C     #   OC    #   OOC   #   OOOC  #  OOOOC #  OOOOOC#  OOOOOO#  OOOOOO#
# ### #   # ### #   #C### #   #C### #  #C### #  #C### #  #O###C#  #O###O#
# ### #   # ### #   # ### #   # ### #  # ### #  # ### #  #C### #  #O###C#
# ###     # ###     # ###     # ###    # ###    # ###    # ###    #C### 
#######   #######   #######   #######  #######  #######  #######  #######

Answer 1

通常，您不会在 BFS 中同时扩展路径。相反，您将第一个元素放入队列，然后迭代地从前面弹出第一个元素，然后将所有元素添加到队列的后面，这些元素可以从该元素到达但尚未包含在队列中。

您正在尝试仅在 map 上工作；这对于 BFS 是不可能的。您需要一个包含已访问元素位置的队列以及一种将元素标记为已完成的方法。

http://en.wikipedia.org/wiki/Breadth-first_search有一个很好的例子。