矩阵遍历必须命中某些单元格的规则。面试

Question

如果ArraN约束: a，则需要从(0,0)到(N1，N1)之间的矩阵，其中包含白色细胞、黑色细胞和一个灰色细胞。路径应该只覆盖白细胞，并且应该通过灰色单元格。访问过的节点不能再次访问。

白细胞代表0，黑细胞代表1，灰色细胞代表2。

根据我的研究，BFS行不通。我不知道如何让DFS解决这个问题。有些人建议进行搜索，但我不知道如何将其部署到这里。有人认为，首先要找到通往灰色细胞的最短路径，然后从灰色细胞中找到通往N-1，N1的最短路径。但我相信这在某些情况下行不通，因为灰色细胞的最短路径阻碍了从灰色细胞到目标细胞的路径。例如,

-1 => start 
-2 => destination
0 => white space
1 => black space
2 => grey space

-1 0 0 0 0 
0  0 0 1 0 
0  1 0 2 0 
0  1 1 1 1 
0  0 0 0 -2

解决这一问题的方法是采取较长的路径(从正方形的源到右边，下降到2行，然后到2)到灰色单元格，然后从那里到目的地。

请给我爪哇。

Answer 1

对于像您这样的小问题，DFS应该足够好。从你现在的位置往四个方向走就行了。如果你撞到了墙壁，从矩阵上走出来，或者重新访问一个细胞，立即返回。在离开牢房之前，将其标记为已访问的。(在返回之前不要忘记清除该标志，以便其他分支可以使用该单元格。)

这将给你所有可能的道路，而不仅仅是最短的。当然，你必须跟踪这条路，这样当你到达目的地时，你就可以用它做一些事情。您还必须跟踪您是否通过灰色广场，并只考虑有效的路径时，到达目的地。

编辑：在伪代码中，算法如下所示：

traverse(curr, dest, path, pass):
    # curr: current cell
    # dest: destination cell
    # path: path, ie list of cells up to now
    # pass: have we passed the grey cell?

    # stop recursion short
    if curr is out of bounds: return
    if curr is impassable: return
    if curr is visited: return

    # treat cell as visited and add to path
    mark curr as visited
    path = path + [curr]
    if curr is grey: pass = true

    if curr is dest:
        if pass: add path to solution
    else:
        traverse(adj(curr, N), dest, path, pass)
        traverse(adj(curr, E), dest, path, pass)
        traverse(adj(curr, W), dest, path, pass)
        traverse(adj(curr, S), dest, path, pass)

    # clean up athis path for other recursions
    mark curr as not visited
    path = path[:-1]

您可以从以下内容开始搜索：

traverse(start, dest, [], false)

哪里写着add path to solution，这取决于你想要什么。您只需打印路径(可能会异常中止递归)，可以将其添加到解决方案的全局列表中，也可以将另一个列表传递给函数并将其添加到此列表中。函数adj(cell, dir)返回一个相邻的单元格；这只是表示类似于(x, y + 1)的东西的一种奇特的方式。

您要求使用Java解决方案，我对此并不熟悉，所以在这里我不能给您提供任何实用的建议。单元格坐标应该是元组，路径应该是单元格的向量，是否可以在一组中检查是否访问了一个单元格。您比我更了解Java数据结构。

Answer 2

看起来是一个最小成本的最大流量问题。将矩阵建模为一个图，在每个连接单元之间有成本1和容量1的边，并在结果图上运行最小成本最大流算法。

当然，由于每个边的代价是1，所以这个问题就变成了一个最大流问题，可以通过埃德蒙兹-卡普来解决。

Answer 3

A怎么了？这个想法很简单。

作为您的初始列表，您只有白色单元格。然后你让A*找出从开始到灰色细胞的方法。一旦找到了路径，您就可以从灰色单元格到末尾进行相同的操作，但不仅从列表中移除黑色单元格，还可以从您已经去过的地方删除黑色单元格。

但是，我不会为你实现A*。看看维基百科和Java实现。

还请注意，A*可能过高，因为所有步骤都具有相同的权重，因此最好考虑考虑这一点的算法。