公式解説と本質的には同じです。

同じフロアの上下左右に隣接するマスを結合することで、問題は次のようになります。

「頂点に重みのついたDAGが与えられる。辺を高々1度逆走してよいとき、各頂点を始点とする経路に含まれる頂点の重みの和の最大値は？」

次のDPを考えます。

• \(\mathrm{DP}_0[v]\)：\(v\) からスタートし、逆走することなく移動したときの、経路に含まれる頂点の重みの和の最大値
• \(\mathrm{DP}_1[v]\)：\(v\) からスタートし、1回目の移動で逆走し、その後は逆走することなく移動したときの、経路に含まれる頂点の重みの和の最大値
• \(\mathrm{DP}_2[v]\)：\(v\) からスタートし、1回目の移動では逆走せず、それ以降で高々1度逆走してよいときの、経路に含まれる頂点の重みの和の最大値

求めるものは \(\max(\mathrm{DP}_2[v],\mathrm{DP}_1[v])\) です。

頂点 \(v\) の重みを \(A_v\)、頂点 \(v\) から移動可能な頂点の集合を \(D_v\) 、逆走で移動可能な頂点の集合を \(D'_v\) とすると、おおよそ次のような関係が成り立ちそうです。

• \(\mathrm{DP}_0[v]=A_v+\max_{u\in D_v}\mathrm{DP}_0[u]\)
• \(\mathrm{DP}_1[v]=A_v+\max_{u\in D'_v}\mathrm{DP}_0[u]\)
• \(\mathrm{DP}_2[v]=A_v+\max_{u\in D_v}\max(\mathrm{DP}_1[u],\mathrm{DP}_2[v])\)

しかし、このままでは正しくありません。
\(\dots\to v_2 \xrightarrow{逆走} v_1 \to v_2 \to v_3 \to \dots\) のような経路に対して、もらうDPで \(\mathrm{DP}_1[v_2]\leftarrow \max(\mathrm{DP}_1[v_2], A_2+\mathrm{DP}_0[v_1])\) としてしまうと、\(A_{v_2}\) が二重にカウントされてしまうためです。

例：

3 1 3
1#1
111
111
1
1 1 1

これを防ぐために、DPの値として「最大値を達成するのは次にどの頂点に移動したときか」も保持し、同じ頂点に戻ってくるときは二重カウントしないようにします。

そうすると今度は、二重カウント防止のために引かれた \(A_v\) により最大値が最大値でなくなってしまう可能性があります。対策として、最大値だけでなく、次に移動する頂点が異なる2ndmaxまで持つようにすることで、最適解を求めることができます。