3

我正在尝试将迷宫数据结构转换为图形。迷宫就像一个网格，细胞之间有一些墙壁。

maze[8][8][4] is how the maze is represented.
If maze[i][j][0] = 1 it means you can't go up from (i,j)
if maze[i][j][1] = 1 it means you can't go down from (i,j)
// and so on

我想把这个迷宫转换成图表我该怎么做？

4

4 回答 4

3

你可以通过两种方式做到这一点：

1.从您的初始矩阵创建一个邻接矩阵。邻接矩阵的形式为：

h[i][j] = 0, if there is no direct link from i to j 
(i and j are not neighbors in the maze)
h[i][j] = 1, if there is a direct link from i to j 
(i and j are neighbors in the maze)

2.为每个节点创建邻居列表：在和之间是否有直接链接j的邻居列表中。iij

于 2012-05-19T14:35:33.980 回答
2

将输入数据视为邻接矩阵。将迷宫想象成一条路径，每个连接段都会创建顶点。并且每个角都是一个节点（包括开始和结束），如果连接存在，则矩阵中有一个值。如果不是，您可以使用 INF 或 -1 来判断没有路由。无论如何，您可以使用 Dijkstra 的最短数学算法来解决这个问题。网络上有很多关于它的信息。

http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/

于 2012-12-10T16:17:51.733 回答
1

对于每个相邻单元格，如果它们之间没有墙，则使它们在图中连接。

于 2012-05-19T14:35:38.880 回答
0 
    game=[[1,1,1,1,1,1,1],
         [1,'A',1,1,0,0,1],
         [1,0,0,0,0,1,1],
         [1,0,0,1,1,1,1],
         [1,1,0,0,0,'B',1],
         [1,1,1,1,1,1,1]]
    rows=len(game)
    cols=len(game[0])
    graph={}
    for i in range(1,rows-1):
       for i in range(1,rows-1):
          if(game[i][j]!=1):
          adj=[]
          for ele in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
               if game[ele[0]][ele[1]] == 0 or game[ele[0]][ele[1]]=='B' :
                       adj.append((ele[0],ele[1]))
          graph[(i,j)]=adj
    print(graph)

    {(1, 1): [(2, 1)],
    (1, 4): [(2, 4), (1, 5)],
    (1, 5): [(1, 4)],
    (2, 1): [(3, 1), (2, 2)],
    (2, 2): [(3, 2), (2, 1), (2, 3)],
    (2, 3): [(2, 2), (2, 4)],
    (2, 4): [(1, 4), (2, 3)],
    (3, 1): [(2, 1), (3, 2)],
    (3, 2): [(2, 2), (4, 2), (3, 1)],
    (4, 2): [(3, 2), (4, 3)],
    (4, 3): [(4, 2), (4, 4)],
    (4, 4): [(4, 3), (4, 5)],
    (4, 5): [(4, 4)]}

我添加了大小为 1 的填充以使代码更简单，迷宫的实际大小为 (row-1,cols-1)，

于 2020-05-01T16:46:08.997 回答