TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2036
  • Problem
  • P2036【CQOI2012】交换棋子
    Limits : Time Limit : 20000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    样例输入1:
    3 3
    110
    000
    001
    000
    110
    100
    222
    222
    222

    样例输入2:
    5 6
    011101
    110000
    000011
    000000
    100000
    110100
    000011
    000000
    110001
    000010
    305713
    537211
    352421
    242212
    333313

    Sample Output

    样例输出1:
    4

    样例输出2:
    10