F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 2668. -- [cqoi2012]交换棋子

2668: [cqoi2012]交换棋子

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1567  Solved: 651
[Submit][Status][Discuss]

Description

有一个nm列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。

Input

第一行包含两个整数nm(1<=n, m<=20)。以下n行为初始状态,每行为一个包含m个字符的01串,其中0表示黑色棋子,1表示白色棋子。以下n行为目标状态,格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串,表示每个格子参与交换的次数上限。
 

Output

输出仅一行,为最小交换总次数。如果无解,输出-1。

Sample Input

3 3
110
000
001
000
110
100
222
222
222

Sample Output

4

HINT

Source

[Submit][Status][Discuss]

HOME Back