📄 trans_cpp.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0065)http://algorithm.fzu.edu.cn/优秀作业和报告/1/S060321095/trans.cpp -->
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.3086" name=GENERATOR></HEAD>
<BODY><PRE>#include <iostream.h>
#include <fstream.h>
bool song(int,int);
int k1,m,n,count,min_count;//k1用来存输入的组数，m,n分别指矩阵的行数和列数，count存变换次数，min_count存最大变换次数。
int **p,**q,**r;
bool match;
void main()
{ ifstream fin("input.txt");//读入文件流input.txt
ofstream fout("output.txt");//输出文件流output.txt
fin>>k1;//输入第一个整数k1
int i,j,x,y,a,b;
int ii,temp,i1,i3,temp1;
for(i=1;i<=k1;i++)
{ fin>>m>>n;//输入行和列
min_count=m+n+1;//？//
p=new int*[m]; //动态分配数组p为源矩阵，q为目标矩阵，r为临时矩阵
q=new int*[m];
r=new int*[m];
for(j=0;j<m;j++)
{ p[j]=new int[n];
q[j]=new int[n];
r[j]=new int[n];
}
for(x=0;x<m;x++) //从input文件中读数据到源矩阵
{
for(y=0;y<n;y++)
{ fin>>p[x][y];
}
}
for(x=0;x<m;x++) //从input文件中读数据到目标矩阵
{
for(y=0;y<n;y++)
{
fin>>q[x][y];
r[x][y]=q[x][y];//把目标矩阵赋值给临时矩阵
}
}
//算法分析与思路
min_count=m+n+1; //初始化变换次数为最坏情况
for(x=0;x<n;x++) //大循环开始---枚举源矩阵每一列变换为目标矩阵每一列的情况，分别统计变换次数，取最少的那个。
{
for(a=0;a<m;a++)
for(b=0;b<n;b++)
q[a][b]=r[a][b]; //每枚举一次都要将目标矩阵恢复原状。
count=0;
for(ii=0;ii<m;ii++)
{
temp=q[ii][0];
q[ii][0]=q[ii][x];//把目标的每一列与第一列交换
q[ii][x]=temp;
}
if(0!=x)
count++;//如果有列转换就执行此句
for(a=0;a<m;a++)
{
if(p[a][0]!=q[a][0])//如果源矩阵不等于目标矩阵
{
for(i3=0;i3<n;i3++)
{
if (q[a][i3]==0)
{
q[a][i3]=1; // 金币翻转行
}
else
{
q[a][i3]=0;
}
}
count++;//如果执行if语句有金币翻转
}
} //count=2
for(a=0;a<n;a++)//break2
{
match=false;
for(b=a;b<n;b++)// break跳出 1
{
if(song(a,b))// 如果两列相等
{
for(i1=0;i1<m;i1++)
{
temp1=q[i1][a];
q[i1][a]=q[i1][b];// 两列互换
q[i1][b]=temp1;
}
if(a!=b)
count++;//目标与源列对比有相等但列的位置不一样执行
match=true;
break;// 跳出1
}
}
if(!match)// 如果找不到两列相等就执行此语句
break; // 跳出 2
}
if((match)&&(count<min_count))
{
min_count=count;// 取最后成功匹配的值
}
}
if(min_count<m+n+1)
{
fout<<min_count<<endl;
}
else
{
fout<<"-1"<<endl;
}
}
delete[]p;
delete[]q;
delete[]r;
}
//判断两列是否相等
bool song(int x,int y)
{
int i;
for(i=0;i<m;i++)
if(p[i][x]!=q[i][y])
return false;
return true;
}
</PRE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -