各 \(x,y\) について，マス \((x,y)\) に到達するまでに拾うコインの最大値と最小値は \(O(N^2)\) の dp で簡単に計算できます．

実は，以下が成り立ちます．

• マス \((x,y)\) の最小値を \(m\)，最大値を \(M\) とする．このとき，任意の \(k\ (m\leq k\leq M)\) について，\((x,y)\) に到達するまでにちょうど \(k\) 枚拾うような移動方法が存在する．

（証明）
移動方法を D と R で表現することにする．最小値，最大値を達成する DR 列を \(X,Y\) とする．このとき，隣接 swap を繰り返すことで \(X\) を \(Y\) にすることができる．この過程を \(X=P_0\to P_1\to P_2\to \ldots \to P_{K-1}\to P_{K}=Y\) とする．このとき，\(P_i\) と \(P_{i+1}\) は通るマスがちょうど \(1\) 箇所変更されており，ゆえに拾うコインの枚数は高々 \(1\) しか違わない．したがって，中間値の定理よりちょうど \(k\) 枚拾うような移動経路 \(P_i\) が必ず存在する．