#1518. 逗猫

逗猫

题目描述

小 w 和男朋友一起养了 n×mn \times m 只猫,这些猫被排成了一个 n×mn \times m 的矩阵。

天气转凉,猫咪需要戴上帽子,帽子有黑白两种颜色。由于猫咪很傲娇,有时它们希望上下左右的相邻猫有奇数只戴着白帽子,有时希望相邻的猫有偶数只戴着白帽子

现在猫咪们被小 w 的男朋友胡乱戴上了帽子。小 w 很头疼,于是向你求助,希望你给出一种猫咪更换帽子颜色的方案,使得猫咪们的需求能被满足,同时需要被更换帽子的猫咪尽可能少。

输入格式

第一行三个整数 n,m,cn, m, c ,表示猫咪被排成了一个 n×mn \times m 的矩阵,当 c=0c = 0 时,猫满意的条件是都希望相邻的猫有偶数只戴着白帽子, c=1c = 1 时它希望相邻的猫有奇数只戴着白帽子。

接下来 nn 行,每行 mm 个数,表示矩阵中每只猫戴着帽子的颜色。 00 代表黑帽子, 11 代表白帽子。

输出格式

输出一行一个数,表示最少要给多少猫更换帽子颜色。

无解输出 1-1

样例

3 4 1
1 1 0 1
0 1 1 0
0 0 0 1
4

一种最优的方案是:

1 1 1 1
0 1 1 0
1 1 1 1

其中有 44 个位置的猫被更换了帽子的颜色。

数据范围与提示

对于前 30%30\% 的数据,n×m18n \times m \le 18
对于另 20%20\% 的数据,n=2n = 2
对于 100%100\% 的数据,1n×m3001 \le n \times m \le 300