TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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