button.cpp

数据结构作业Button

#include <stdio.h>
#include <iostream>
using namespace std;
#define SIZE 100

int t;//数组组数
int n,m;//n行m列
int count;//记录操作次数
int best;//如果能交换的最少操作次数
int b0[SIZE+1][SIZE+1];//初始状态,从第1行第1列开始使用，下同
int b1[SIZE+1][SIZE+1];//目标状态
int b[SIZE+1][SIZE+1];//备份目标状态
bool found;

void reverse(int );//行操作，反色
void exchange(int ,int );//列操作，交换两列
bool same(int ,int );//判断两列是否相同
void acpy(int [SIZE+1][SIZE+1],int [SIZE+1][SIZE+1]);//复制数组，备份
void Swap(int&,int&);//交换两数，被exchange调用

void main()
{
	cin>>t;
	for (int i=1;i<=t;i++)
	{
		cin>>n>>m;
		//输入初始状态目标状态
		for (int x=1;x<=n;x++)
			for (int y=1;y<=m;y++)
				cin>>b0[x][y];
		for (int x=1;x<=n;x++)
			for (int y=1;y<=m;y++)
				cin>>b1[x][y];
		//把目标状态备份到数组b中
		acpy(b,b1);
		best=m+n+1;
		for (int j=1;j<=m;j++)
		{
			acpy(b1,b);//循环一次后，数组b1恢复到目标状态
			count=0;
			exchange(1,j);//第j列和第1列交换
		    
			//使b1中交换后的第1列变成和初始状态一样，即若b1中第p行第1列与目标状态对应位置不一致，行反色
			for (int p=1; p<=n; p++)
			{
				if(b0[p][1]!=b1[p][1])  
					reverse(p);
			}
			//b1的第1列调整得和初始状态一致后，依次考察b0的第p列，是否能在b1中找到对应列，如果找到，记为第q列，在b1中把p,q两列交换
			for (int p=1; p<=m; p++)
			{
				found=false;
				for (int q=p; q<=m; q++ )
				{
					if( same(p,q) )
					{
						exchange(p,q);
						found=true;
						break;
					}
				}
			
			if (!found) break;
			}
		if(found && count<best) best=count;
		//if(found && count<best) break;//只要找到一中交换方法，就退出

		}
		if( best<m+n+1 )cout<<"Yes"<<endl;
			else
				cout<<"No"<<endl;
	}
	
}

//行操作，反色第x行
void reverse(int x)
{
	for (int i=1;i<=m;i++) b1[x][i]=b1[x][i]^1;
	count++;
}

//列操作，交换x,y两列
void exchange(int x,int y)
{
	for(int i=1;i<=n;i++)
		Swap(b1[i][x],b1[i][y]);
	if(x!=y)count++;
}

//判断x,y两列是否相同
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[SIZE+1][SIZE+1],int b[SIZE+1][SIZE+1])
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=b[i][j];
}

//交换两数，被exchange调用
void Swap(int&a,int&b)
{
	int temp; 
	temp=a; 
	a=b; 
	b=temp;
}