QHQ-【问题描述】有m*n(m<=100, n<=100)枚金币在桌面上排成一个m行n列的金币矩阵。每枚金币或正面朝上或背面朝上。用数字表示金币状态,0表示金币正面朝上,1表示金币背面朝上。

金币矩阵游戏的规则是:1.每次可将任一行金币翻转过来放在原来的位置上;2.每次可任选2列,交换着2列金币位置。

算法设计:给定金币阵列的初始状态和目标状态,计算按金币游戏规则,将金币阵列从初始状态转换到目标状态所需要的最小变换次数。


```
问题描述】有m*n(m<=100, n<=100)枚金币在桌面上排成一个m行n列的金币矩阵。每枚金币或正面朝上或背面朝上。用数字表示金币状态,0表示金币正面朝上, 1表示金币背面朝上。

金币矩阵游戏的规则是:1.每次可将任一行金币翻转过来放在原来的位置上;2.每次可任选2列,交换着2列金币位置。

算法设计:给定金币阵列的初始状态和目标状态,计算按金币游戏规则,将金币阵列从初始状态转换到目标状态所需要的最小变换次数。
【输入形式】第1行有2个正整数m和n,用#隔开。以下m行是金币阵列的初始状态,每行有n个数字表示该行金币的状态,0表示正面朝上,1表示背面朝上。接着的m行是金币阵列的目标状态,不用#隔开  。
【输出形式】输出计算出的最小变化次数。相应数据无解是,输出-1 。
【样例输入】

4#3

101

000

110

101
101

111

011

101
【样例输出】2

```

```

#include <fstream>
#include <iostream>
using namespace std;
const int size1 = 100;
int k, n, m, ccount, best;
int b0[size1 + 1][size1 + 1], b1[size1 + 1][size1 + 1], b[size1 + 1][size1 + 1];
bool found;

void stringToInt(string str,int& n,int& m)
{
    int len = str.length();
    int temp = 0;
    for(int i = 0; i < len; i++)
    {
        if(str[i] != '#')
        {
            temp = temp * 10 + (int)str[i] - 48;
        }
        else
        {
            n = temp;
            temp = 0;
        }
    }
    m = temp;
}
void trans1(int x)   // 行翻转
{
	for (int i = 1; i <= m; i++)
        b1[x][i] = b1[x][i] ^ 1;
	ccount++;
}
void trans2(int x, int y)   // 列交换
{
	for (int i = 1; i <= n; i++)
        swap(b1[i][x], b1[i][y]);
	if (x != y) ccount++;
}
bool same(int x, int y)
{
	for (int i = 1; i <= n; i++)
        if (b0[i][x] != b1[i][y])
            return false;
	return true;
}
void acpy(int a[size1 + 1][size1 + 1], int b[size1 + 1][size1 + 1])
{
	for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = b[i][j];
}
void answer()
{
	int x, y, j, p;
        //cin >> n >> m;
        string str;
        int temp = 0;
        cin >> str;
        stringToInt(str, n, m);
        // 原状态   b0
        for (x = 1; x <= n; x++) {
            cin >> temp;
            for (y = 1; y <= m; y++) {
                b0[x][y] = temp % 10;
                temp /= 10;
                //cin >> b0[x][y];
            }
        }
        // 目标状态   b1
        for (x = 1; x <= n; x++) {
            cin >> temp;
            for (int y = 1; y <= m; y++) {
                b1[x][y] = temp % 10;
                temp /= 10;
                //cin >> b1[x][y];
            }
        }
        acpy(b, b1);
        best = m + n + 1;
        for (j = 1; j <= m; j++)
        {
            acpy(b1, b);
            ccount = 0;
            trans2(1, j); // 列变换
            int p;
            for (p = 1; p <= n; p++)
                if (b0[p][1] != b1[p][1])
                    trans1(p); // 行变换
            for (p = 1; p <= m; p++)    //找列相等的( b1 的 q 列和 b0 的 p 列相等)
            {
                found = false;
                for (int q = p; q <= m; q++)
                    if (same(p, q))
                    {
                        trans2(p, q);
                        found = true;
                        break;
                    }
                if (!found) break;
            }
            if (found && ccount < best)
                best = ccount;
        }
        if (best < m + n + 1) {
            cout << best << endl;
        }
        else {
            cout << -1 << endl;
        }
	//}
}
int main()
{
	answer();
	return 0;
}
```

StringToint() 函数获取输入的特殊格式,并分发数据给行n,列m。

trans1()trans2() 为行转换与列转换。