tran.cpp

有m&acute n(m <=100,n <= 100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金 币或正面朝上或背面朝上。用数字表示金币状态

#include<iostream>
#include <fstream>
//#include<ctime>
using namespace std;

//clock_t start,end;  //用来测时间
int count;      //记录变换次数
int min_count;  //记录最小变换次数
bool found;      //标记是否发现两列相同

void swap(int &a ,int &b)///////对换两个数
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void change_row(int **a,int n,int x)//翻转行
{
	for(int i=0;i<n;i++)
	{
		if(a[x][i]==0)
			a[x][i]=1;
		else if(a[x][i]==1)
			a[x][i]=0;
	}
	count++;
}

void swap_rol(int **a,int m,int x,int y)////交换两列
{

	for(int i=0;i<m;i++)
	{
		swap(a[i][x],a[i][y]);
	}
	if(x!=y)
		count++;
}

bool isSame(int **a,int **b,int m,int x,int y)////判断两列是否相等
{
	for(int i=0;i<m;i++)
	{
		if(a[i][x]!=b[i][y])
		return false;
	}
	return true;
}

void copy_array(int **a,int **b,int m,int n)///复制备份
{
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			a[i][j]=b[i][j];
}

//-------------------------------------------------------------------------
//-----------以下是主函数--------------------------------------------------

void main()
{
/////////////////////////////////////////////导入input.txt
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");
///////////////////////////////////////////////////////////////
//	start=clock();
	int num,m,n;////////num为输入测试数据的组数,m为行数,n为列数
	in>>num;
	for(int k=0;k<num;k++)////动态分配数组
	{
		in>>m>>n;
		int **a1=new int *[m];
		int **a2=new int *[m];
		int **b1=new int *[m];
		int **b2=new int *[m];
		for(int i=0;i<m;i++)
		{
			a1[i]=new int [n];
			a2[i]=new int [n];
			b1[i]=new int [n];
			b2[i]=new int [n];
		}
		
		for(i=0;i<m;i++)
			for(int j=0;j<n;j++)
				in>>a1[i][j];

		for(i=0;i<m;i++)
			for(int j=0;j<n;j++)
				in>>a2[i][j];	
		

/////-----------------数据输入完成-------------------------------------------------

		copy_array(b1,a1,m,n);///复制备份
		copy_array(b2,a2,m,n);
		min_count=m+n+1;
		for(i=0;i<n;i++)
		{
			copy_array(a1,b1,m,n);//复制
			copy_array(a2,b2,m,n);//复制
			count=0;//从0开始计算
			swap_rol(a1,m,0,i);//交换列
			for(int j=0;j<m;j++)//如果遇到不相等的.翻转行
			{
				if(a1[j][0]!=a2[j][0])
				{
					change_row(a1,n,j);
				}
			}
			for(j=0;j<n;j++)//循环比较
			{
				found=false;
				for(int p=j;p<n;p++)
				{
					if(isSame(a1,a2,m,j,p))
					{						
						swap_rol(a2,m,j,p);
						found=true;
						break;
					}
				}
				if(!found)
					break;
			}
			if(found && count<min_count)//取最小的次数
				min_count=count;
		}
		if(min_count<m+n+1)//输出正确结果最小次数
			out<<min_count<<endl;
		else
			out<<-1<<endl;//无解情况输出-1
		for(i=0;i<m;i++)//释放内存
		{
			delete [] a1[i];
			delete [] a2[i];
			delete [] b1[i];
			delete [] b2[i];
		}
        delete [] a1;
		delete [] a2;
		delete [] b1;
		delete [] b2;
	}
//	end=clock();
//	cout<<end-start<<endl;
}