E
一个 $n\times m\le 3\times 10^5$ 的网格，里面有一些 $1$，其余是 $0$，你需要填上尽可能少的 $1$，让网格上下不连通，并且 $1$ 之间边不相邻。
这道题还是发现我网格图图论不扎实的问题。
首先很容易想到一定会存在一条自左到右的链，分隔了上下两部分。所以我直接从左到右 $DP$。
但是得到了 $WA2$ 的好成绩。
左思右想也找不出问题，但是对拍后发现似乎是可以往回走的。
改成最短路算法就通过了。
矩阵图论的题目，不要只看到自左向右，要考虑存不存在往回的可能。
如果没有错过，确实很难意识到这种思维漏洞，所以一定要记住！