P2598 [ZJOI2009] The Story of the Wolf and the Sheep

“The wolf fell in love with the sheep, madly in love; after all, they truly loved once. The wolf fell in love with the sheep; it isn’t absurd. They say where there is love, there is direction...” Hearing this song, Orez thought: since wolves and sheep are so harmonious, why not try raising them together? So he decided to give it a try. Orez’s wolf-and-sheep pen can be viewed as an $n\times m$ grid. Fences have already been installed along the outer boundary of this grid. However, Drake quickly realized that wolves are still wolves—they always covet the sheep—and that song is just a moving legend. So Orez decided to add some more fences inside the pen to keep the wolves and sheep separated. After careful observation, Orez found that both wolves and sheep each have their own territories. If they cannot stay within their own territory, they become very irritable, which is not good for their growth. Orez wants the added fences to be as short as possible. Of course, these fences must first ensure that the ownership of wolves’ and sheep’s territories does not change; second, the fences must be built completely—specifically, they must lie along the edges of unit cells and cannot be built only partially.

The first line contains two integers $n$ and $m$. Then follow $n$ lines, each containing $m$ integers: $1$ indicates that the cell belongs to the wolves’ territory, $2$ indicates that it belongs to the sheep’s territory, and $0$ indicates that the cell belongs to neither animal.

Output a single integer $\mathit{ans}$, representing the shortest total length of the fence.

For $10\%$ of the testdata, $n, m \le 3$. For $30\%$ of the testdata, $n, m \le 20$. For $100\%$ of the testdata, $1 \le n, m \le 100$. Translated by ChatGPT 5