C++金币阵列

C++金币阵列

Scroll Down

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() 为行转换与列转换。