java - 在矩阵中查找其元素总和为给定数字的路径

Question

给定一个 M x N 矩阵和一个正整数 p，我如何通过从位置 0,0< 开始的矩阵递归地找到一条连续路径 总和为 p？您可以向左 (col - 1)、向右 (col + 1)、向上 (row - 1) 或向下 (row + 1) 移动，并且只能在路径中使用一次位置。如果矩阵中存在这样的路径，则将其输出到具有相同形状的单独矩阵中，路径上的位置用 1 填充，其余位置用 0 填充。

我真的愣住了，什么都做不了，请问有什么技巧可以解决这类问题吗？如何继续解决这个问题，我们将不胜感激。

这是一个示例，其中 p = 73:

2  8  15 
1  10 5
19 19 3  
5  6  6
2  8  2

输出:

1  0  0
1  0  0
1  1  1
1  1  1
1  1  1

Answer 1

“应该随机移动”(可能是故意的)具有误导性。你想要做的是有效的深度优先搜索，系统地测试可能的路线。如果路线等于(您已完成)或超过目标数量，则该路线终止，在这种情况下您将后退。

如果我们假设路线不能自行折回(您没有说)，那么可以使用左(或右)边缘跟随模式，就像标准迷宫求解器一样。因此，在访问的每个新节点处，它会继续到最左侧未访问的相邻节点，随后以顺时针方向尝试其他相邻节点。

(如果路线可以重新访问节点，则将矩阵视为四叉树并选择任意方向首先进行测试。)