有一个矩阵包含白细胞，黑细胞和只有一个灰色细胞，如果arra[n][n]，则需要从（0,0）到（n-1，n-1）
限制条件：
A.路径应仅覆盖白细胞，并应通过灰色细胞。
b.访问过的节点不能再访问。
白细胞用0表示，黑细胞用1表示，灰细胞用2表示。
根据我的研究，男朋友是行不通的。我不知道如何让dfs解决这个问题。有人建议搜索，但我不知道如何在这里部署。有人提出，首先找到灰色单元的最短路径，然后从灰色单元找到到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）到灰色单元格，然后从那里到目的地。
请给我爪哇。
最佳答案
对于像你这样的小问题，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数据结构。