TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2028
  • 题目
  • P2028【CQOI2012】交换棋子
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    样例输入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

    样例输出

    样例输出1:
    4

    样例输出2:
    10