维普资讯 http://www.cqvip.com 缩疆托■ 臻爨醒嚣鹾麓暑辨 孵 器 数字迷宫是一个非常有趣的算法 习 曩，读者如果能充分掌曩其ｔ奉思路，兜全 可以 出结合圈形的各掌Ｕ毫宫 游戏程序。本文 Ｅ者将结合．藿Ｕ手来 ．｜留谈算 法的Ｃ语言实现。 ［ｆ【ｒ１］．ｎ岫相加即为ｔｏｔａｌ，ｐｏｉｎｔ指向相加的那个数。这样 从ａ［ｎ］［ｍ］计算到ａ［１］［１］，每一个格的ｔｏｔａｌ都是最优解， 最后只需输出即可。 有一数字组成的迷宫，ｎ行ｍ列，假定有一人从左下角 （坐标：１，１）走到右上角（坐标ｎ，ｍ），只允许向右或向 总求解过程流程图如图１所示： 上走，求一条路线，使该人走过的数字和为最大。 比如当输入以下数字，构成数字迷宫： ｍ＝３，ｎ＝３ ２、 １、４ ５、７、９ １ ０、 １、３ 运行结果为： （１，１）一（２，１）一（２，２）一（２，３）一（３，３）—：２６ 该题如果使用穷举算法显然速度太慢，笔者推荐使用动 态规划方法，具体如下所述： 设有迷宫结构数组ａ［ｎ］［ｍ］，用ａ［ｉ］［ｊ］．ｎ岫表示迷宫中 的数字，ａ［ｉ］［Ｊ］．ｔｏｔａｌ表示从ａ［ｉ］［ｊ］走到ａ［ｎ］［ｍ］能经过的 最大数字和，ａ［ｉ］［Ｊ］．ｐ０ｉｎｔ表示走到ａ［ｉ］［Ｊ］后应向哪个方 向走。ａ［ｎ］［ｍ］．ｔｏｔａｌ显然等于ａ［ｎ］［ｍ］．ｎ岫，将ｐ０ｉｎｔ设为 ０表示不再走。ａ［ｎ］［旷１］只能向左走，ｔｏｔａｌ为ｎ岫和ａ［ｎ］ ［ｍ］．ｔｏｔａｌ的和，以此类推。ａ［ｎ－１］［ｍ一１］要视ａ［ｎ－１］［ｍ］． ｔｏｔａｌ和ａ［ｎ］［ＩＩｒ１］．ｔｏｔａｌ中的大者而定，取其大者与ａ［ｎ－１］ 图１ 维普资讯 http://www.cqvip.com
