寻找一个路径，其元素在矩阵中总计为给定的数字 [英] Finding a path whose elements sum up to a given number in a matrix

问题描述

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

Given a M x N matrix and a positive integer p, how can I find a continuous path recursively through the matrix starting at position 0,0 that will sum to p? You can move left (col - 1), right (col + 1), up (row - 1) or down (row + 1), and can only use a position once in the path. If there is such path in the matrix, output it in a separate matrix with the same shape, by filling the positions on the path with 1 and the rest positions with 0.

我真的冻结了，什么也做不了，有没有解决这些问题的技术?人们将如何继续解决这一问题，我们将不胜感激.

I literally froze and could do anything, is there any technique for solving these kinds of problems? How would one go on about approaching this problem, a solution would be much appreciated.

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

Here is an example where 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

推荐答案

应该随机移动"具有误导性(可能是故意的).您要做的是有效地进行深度优先搜索，系统地测试可能的路线.如果路由等于(完成)或超过目标数目，则该路由终止，在这种情况下，您将进行备份.

"Should randomly move" is (possibly intentionally) misleading. What you want to do is effectively a depth-first search, systematically testing possible routes. A route terminates if it equals (you're done) or exceeds the target number, in which case you back up.

如果我们假设路线不能重返自身(您未说)，那么可行的是左(或右)边跟随模式，例如标准迷宫求解器.因此，在每个访问的新节点处，它都会前进到最左边未访问的相邻节点，然后按顺时针方向尝试其他相邻节点.

If we assume the route can't double back on itself (you didn't say), then what would work is a left- (or right-) edge following pattern, like a standard maze solver. So at each new node visited, it proceeds to the left-most non-visited adjacent node, subsequently trying other adjacent nodes in a clockwise direction.

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

(If the route can revisit nodes, then treat the matrix as a 4-tree and pick an arbitrary direction to test first.)

这篇关于寻找一个路径，其元素在矩阵中总计为给定的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！