302216: CF425B. Sereja and Table
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Sereja and Table
题意翻译
给定一个 $ n\times m $ 的矩阵,每个格子有黑白两种颜色,要求修改不超过 $k$ 个格子的颜色,使得任意一个同色极大连通块都为矩阵(在矩阵中有公共边即为相邻),求最少的修改次数,如果这个次数超过了 $k$ 则输出 $-1$。题目描述
Sereja has an $ n×m $ rectangular table $ a $ , each cell of the table contains a zero or a number one. Sereja wants his table to meet the following requirement: each connected component of the same values forms a rectangle with sides parallel to the sides of the table. Rectangles should be filled with cells, that is, if a component form a rectangle of size $ h×w $ , then the component must contain exactly $ hw $ cells. A connected component of the same values is a set of cells of the table that meet the following conditions: - every two cells of the set have the same value; - the cells of the set form a connected region on the table (two cells are connected if they are adjacent in some row or some column of the table); - it is impossible to add any cell to the set unless we violate the two previous conditions. Can Sereja change the values of at most $ k $ cells of the table so that the table met the described requirement? What minimum number of table cells should he change in this case?输入输出格式
输入格式
The first line contains integers $ n $ , $ m $ and $ k $ $ (1<=n,m<=100; 1<=k<=10) $ . Next $ n $ lines describe the table $ a $ : the $ i $ -th of them contains $ m $ integers $ a_{i1},a_{i2},...,a_{im} $ $ (0<=a_{i,j}<=1) $ — the values in the cells of the $ i $ -th row.
输出格式
Print -1, if it is impossible to meet the requirement. Otherwise, print the minimum number of cells which should be changed.
输入输出样例
输入样例 #1
5 5 2
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
输出样例 #1
1
输入样例 #2
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0
输出样例 #2
-1
输入样例 #3
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1
输出样例 #3
0