Skip to content

1204: 狼和羊

题目

题目描述

有一个长方形牧场,我们将其视为一个大小为$n\times m$的矩形,这个牧场的边缘已经装上了篱笆。 我们需要在这个牧场里同时养狼和羊,所以需要再加入一些篱笆,将羊狼分开。 在这个牧场里,狼和羊都有属于自己的领地,我们想要在添加篱笆的尽可能短的前提下,将狼和羊的领地分开。 篱笆必须修建在格子的边界上,并且不能只修建一部分,也就是说一次至少要围住一个格子的一面。

输入格式

输入第一行包含两个整数$n$和$m$,表示牧场的大小。
接下来$n$行,每行$m$个整数,$1$表示该格子属于狼的领地,$2$表示属于羊的领地,$0$表示该格子不是任何一只动物的领地。

输出格式

输出一个整数,代表篱笆的最短长度。

样例输入

text 2 2 2 2 1 1

样例输出

text 2

数据范围

对于 10\%的数据,保证 $n,m \leq 3$。
对于 100\%的数据,保证 $n,m \leq 30$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!