对于绕圈的,如果这个圈非正,可以贪心去除,那么它绕了一个正圈,一个绕圈路径可以分成很多连续段,也就是有一个连续段之和为正,也就是存在两个相邻的数,他们的和 >0。那么如果第一次碰到这两个格子的时候,碰到第一个格子的时候,肯定是有非负的摩拉,因为我们假设了这条路径,那么再经过另一个点,因为和为正,肯定也是非负的,然后还可以再次经过这两个点,得到形如 x\rightarrow y\rightarrow x\rightarrow y\dots 的路径。“刷摩拉”,一直达到上界 k。那么可以直接把这两个格子中 a 非负的格子的 a 改成 k。(比如 [-2,3]\rightarrow[-2,k],[0,1]\rightarrow[k,k])那么从 (i,j_1) 到 (i,j_2) 要么是直接走,要么就是需要到某个格子刷摩拉走一条左侧的折线或者右侧的折线,来刷摩拉。具体实现从左往右扫,从右往左扫,再从左往右扫即可。
但是这里没有考虑既往左又往右的情况。加上就是完备的,为什么?如果左侧有两个刷币点,那么能够前往最近的,就可以完成满币,不必前往下一个点。右侧同理,所以对于 A\dots S \dots T \dots B 的样子, S 是入口,T 是出口,A,B 是刷币点,可能走出来 SABT,SAT 的路线,本质就是看 A\rightarrow T,B \rightarrow T 哪个更优。每一次转折都一定要刷币,而关键的刷币点只有两个,所以最多转折两次,于是代码就是从左往右扫,从右往左扫,从左往右扫,从右往左扫。