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

Question

有一个包含白色单元格，黑色单元格和只有一个灰色单元格的矩阵，需要从 (0,0) 到 (N-1, N-1) 如果 Arra[N][N]约束:A。该路径应该只覆盖白色单元格并且应该通过灰色单元格。b.访问过的节点不能再次访问。

白色单元格用 0 表示，黑色单元格用 1 表示，灰色单元格用 2 表示。

根据我的研究，BFS 不起作用。我不确定如何让 DFS 解决这个问题。有人建议使用 A* 搜索，但我不确定如何在此处部署它。有人建议首先找到到灰色单元格的最短路径，然后从灰色单元格我们找到到 N-1，N-1 的最短路径。但我相信这在某些情况下不起作用，因为灰色单元格的最短路径会阻塞从灰色单元格到目标单元格的路径。例如，

-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)到灰色单元格，然后从那里到目的地。

请使用 Java。

Answer 1

看起来像最小成本最大流问题。将您的矩阵建模为图形，其中每个连接的单元格之间的边成本为 1，容量为 1，并在生成的图形上运行最小成本最大流算法。

当然，由于每条边的成本为 1，问题就简化为最大流问题，可以用 Edmonds - Karp 来解决.