c# - 二维数组中的寻路

Question

我目前正在从事一个项目，在该项目中我必须使用包含随机数的二维数组执行任务。该数组形成一个网格，代表一座山的山峰(高度)。我解决了除最后一项以外的所有任务:

最后一个任务是查找是否存在从最小的峰到最高的路径(不一定是最短的)。路径应该由不断增长的山峰组成，我不能踩到更低的山峰。

这里有一个示例，为简单起见，在 3x3 网格上表示(原始的要大得多，并且不需要像正方形一样，它是根据用户的需要生成的，数字是完全随机的)。

2  4  5    
1  3  8
9  7  10

可能的方式是 1-3-7-10、1-3-8-10、1-2-4-5-8-10。

我很确定，我应该使用某种递归。我阅读了有关 a* 探路者的信息，但要使用它，我必须有一个带有“障碍”的“ map ”(我无法踏入的节点 = 较小的山峰)，这正是我无法做到的，因为你只会在旅途中发现它。

我的意思是我可以将数字 7 放在“异常(exception)列表”中 - 因为步骤 1-9-7 是被禁止的，但是步骤 1-3-7-10 是完美的，所以将 7 放在异常(exception)列表中是一个错误。

Answer 1

关键是首先将您的数组转换为“有向图”，这是一个根据您的规则仅由有效的单元格到单元格移动组成的有向图。这个二合字母将是一个数组或条目列表，包括:{FromCell, ToCell}

您的二合字母将包含如下数据:

2,4
4,5
5,8
1,2
1,3
1,9
3,4
3,8
3,7
8,10
7,10

从这里您应该能够应用 A* 算法，或任何其他算法。

(注意:我没有发布完整的答案，因为我假设你想自己做)

---

也就是说，您可以使用回溯法进行强力递归搜索。这是最简单的解决方案，但可能不是最有效的。