新闻动态

关卡如果只允许向右或向下移动，即使起终点固定，也可能有多条有效路线。统计能到达某格的路线数，与只判断能否到达不同；障碍会影响它后方多个格子的累计结果。

下面使用独立的一组输入，逐步记录规则如何产生结果。建议先自行推演，再寻找与记录第一次不同的位置；检查时间单位、端点归属和处理顺序。所有约定均限定在本例中，其他作品采用不同实现并不自动意味着出错。

本例约定与输入

从左上角到右下角，只允许右移或下移一格，障碍不可进入；每格路线数为左方与上方有效路线数之和，起点为一，障碍为零。不同方向序列视为不同路线。

地图5×6，S起点、E终点、#障碍 S.##. ....# ##... #.... ..... ..#.E

过程与结果

第0行累计路线数[1, 1, 0, 0, 0]；本行障碍列[2, 3]，障碍格保持零。

第1行累计路线数[1, 2, 2, 2, 0]；本行障碍列[4]，障碍格保持零。

第2行累计路线数[0, 0, 2, 4, 4]；本行障碍列[0, 1]，障碍格保持零。

第3行累计路线数[0, 0, 2, 6, 10]；本行障碍列[0]，障碍格保持零。

第4行累计路线数[0, 0, 2, 8, 18]；本行障碍列[]，障碍格保持零。

第5行累计路线数[0, 0, 0, 8, 26]；本行障碍列[2]，障碍格保持零。

检查格(0,4)：左方贡献0，上方贡献0，合计0，与表中0一致。

检查格(1,4)：左方贡献0，上方贡献0，合计0，与表中0一致。

检查格(4,0)：左方贡献0，上方贡献0，合计0，与表中0一致。

检查格(2,2)：左方贡献0，上方贡献2，合计2，与表中2一致。

检查格(3,3)：左方贡献2，上方贡献4，合计6，与表中6一致。

检查格(2,4)：左方贡献0，上方贡献2，合计2，与表中2一致。

检查格(4,4)：左方贡献8，上方贡献10，合计18，与表中18一致。

终点共有26条有效方向序列。

如何独立复核

枚举包含所需右移和下移次数的所有方向序列，逐条检查障碍，再与逐格累计结果比较。总数为零代表没有路线，不能把它当作计算过程被跳过。

允许向左或向上返回以后，就可能出现环路，路线长度也不再固定，原来的逐行累计不能直接沿用。这里限制方向，正是为了让每格的前置来源已经算好，避免相互依赖。

测试时保留原始数据与中间状态，再只改变一个条件作比较。先检查空状态、相等边界、重复输入和最后一步，再比较整体结果；不要为了让最后的数字相同而跳过前面已经出现的差异。明确规则后，复核才有可以重复的依据。