4

我正在为一场编程比赛做准备,我正在解决一些我过去无法回答的难题。其中之一是国王的迷宫。-50<x<50本质上,您会得到一个代表“令牌”的 NxN 数字数组。您必须从位置 1,1(我假设数组索引中的 0,0)开始并在 N,N 处结束。您必须在您访问的单元格上拾取令牌,并且您不能踩没有令牌的单元格(由 0 表示)。如果你被 0 包围,你就输了。如果迷宫没有解决方案,则输出“无解决方案”。否则,您会输出通过将您拾取的代币相加可以获得的最高数字。

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

另外,提到这个问题是针对高中生的,这可能会有所帮助。

4

3 回答 3

3

这类问题通常使用动态编程记忆化来解决。

基本上,您制定一个递归解决方案,并在记住和重用先前计算的结果的同时自下而上地解决它。

于 2011-04-08T14:06:58.040 回答
1

简单的方法(即最简单的编码)是尝试所有可能的路径 - 尝试每个第一步;对于每个第一步,尝试每个第二步;对于每个第一步/第二步组合,尝试每个第三步;等等。然而,根据迷宫的大小,这可能需要很长时间才能运行(或者可能不会)。

您的下一步是考虑如何更快地做到这一点。第一步通常是消除你知道不会导致完成的动作,或者不能导致比你已经拥有的分数更高的完成。由于这是比赛的练习,我们将让您自己完成这项工作。

于 2011-04-08T14:15:42.720 回答
0

思考“图”算法:算法设计手册

于 2011-04-08T14:14:22.803 回答