题解

核心算法

在位置之外增加 used，表示是否已经经过负数格。

思路推导

当前格正负决定从上一状态的哪一层转移，非法层保持负无穷。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(nm)
• 空间复杂度：O(nm)

易错点

不能用0表示不可达；起点负数也要消耗机会。

完整标程见 std/main.cpp。