关卡如果只允许向右或向下移动,即使起终点固定,也可能有多条有效路线。统计能到达某格的路线数,与只判断能否到达不同;障碍会影响它后方多个格子的累计结果。
下面使用独立的一组输入,逐步记录规则如何产生结果。建议先自行推演,再寻找与记录第一次不同的位置;检查时间单位、端点归属和处理顺序。所有约定均限定在本例中,其他作品采用不同实现并不自动意味着出错。
本例约定与输入
从左上角到右下角,只允许右移或下移一格,障碍不可进入;每格路线数为左方与上方有效路线数之和,起点为一,障碍为零。不同方向序列视为不同路线。
地图5×6,S起点、E终点、#障碍 S.... ..... ..... #...# ...## ....E
过程与结果
第0行累计路线数[1, 1, 1, 1, 1];本行障碍列[],障碍格保持零。
第1行累计路线数[1, 2, 3, 4, 5];本行障碍列[],障碍格保持零。
第2行累计路线数[1, 3, 6, 10, 15];本行障碍列[],障碍格保持零。
第3行累计路线数[0, 3, 9, 19, 0];本行障碍列[0, 4],障碍格保持零。
第4行累计路线数[0, 3, 12, 0, 0];本行障碍列[3, 4],障碍格保持零。
第5行累计路线数[0, 3, 15, 15, 15];本行障碍列[],障碍格保持零。
检查格(4,1):左方贡献4,上方贡献1,合计5,与表中5一致。
检查格(2,4):左方贡献3,上方贡献9,合计12,与表中12一致。
检查格(3,0):左方贡献1,上方贡献0,合计1,与表中1一致。
检查格(3,2):左方贡献6,上方贡献4,合计10,与表中10一致。
检查格(2,5):左方贡献3,上方贡献12,合计15,与表中15一致。
检查格(3,3):左方贡献9,上方贡献10,合计19,与表中19一致。
检查格(2,3):左方贡献3,上方贡献6,合计9,与表中9一致。
终点共有15条有效方向序列。
如何独立复核
枚举包含所需右移和下移次数的所有方向序列,逐条检查障碍,再与逐格累计结果比较。总数为零代表没有路线,不能把它当作计算过程被跳过。
允许向左或向上返回以后,就可能出现环路,路线长度也不再固定,原来的逐行累计不能直接沿用。这里限制方向,正是为了让每格的前置来源已经算好,避免相互依赖。
测试时保留原始数据与中间状态,再只改变一个条件作比较。先检查空状态、相等边界、重复输入和最后一步,再比较整体结果;不要为了让最后的数字相同而跳过前面已经出现的差异。明确规则后,复核才有可以重复的依据。
