题目描述

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

输入格式

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

输出格式

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

3 3
110
000
001
000
110
100
222
222
222

4

提示

没有写明提示

题目来源

没有写明来源