国王迷宫

Question

我正在练习参加编程比赛，我正在解决一些我以前无法回答的难题。其中之一是国王的迷宫。实质上，您会得到一个代表“令牌”的NxN数字-50<x<50。你必须从位置1,1开始（我假设在数组索引中为0,0）并在N，N处结束。您必须在您访问的单元格上拾取令牌，并且您无法踩入没有令牌的单元格（由0表示）。如果你被0包围，你就输了。如果没有解决方案，输出“无解”。否则，您输出的数字可能会从添加的令牌中累积起来。

我不知道如何解决这个问题。我想你可以写一个迷宫算法来解决它，但这需要时间，而在编程比赛中，你只有两个小时才能解决多个问题。我猜猜我缺少某种模式。任何人都知道我应该如何处理这个？

此外，这可能有助于提到这个问题是针对高中生。

Answer 1

这种类型的问题通常使用dynamic programming或memoization来解决。

基本上你制定了一个递归的解决方案，并解决它自下而上，而记住和重复使用以前计算结果。

Answer 2

认为“图形”算法：The Algorithm Design Manual

Answer 3

简单的方法（即，以最简单的代码）是尝试所有可能的路径 - 尝试每个第一步骤;对于每个第一步，尝试每个第二步;对于每个第一步/第二步组合尝试每个第三步;等等。然而，取决于迷宫的大小，这可能需要很长的时间才能运行（或者可能不会）。

您的下一步是想想如何更快地做到这一点。第一步通常是消除你知道不能完成的动作，或者不能达到比已有的动作更高的点。既然这是一场比赛的练习，我们会让你自己去做这项工作。