?? trans_cpp.htm
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0065)http://algorithm.fzu.edu.cn/優(yōu)秀作業(yè)和報(bào)告/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用來(lái)存輸入的組數(shù)，m,n分別指矩陣的行數(shù)和列數(shù)，count存變換次數(shù)，min_count存最大變換次數(shù)。
int **p,**q,**r;
bool match;
void main()
{ ifstream fin("input.txt");//讀入文件流input.txt
ofstream fout("output.txt");//輸出文件流output.txt
fin>>k1;//輸入第一個(gè)整數(shù)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]; //動(dòng)態(tài)分配數(shù)組p為源矩陣，q為目標(biāo)矩陣，r為臨時(shí)矩陣
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文件中讀數(shù)據(jù)到源矩陣
{
for(y=0;y<n;y++)
{ fin>>p[x][y];
}
}
for(x=0;x<m;x++) //從input文件中讀數(shù)據(jù)到目標(biāo)矩陣
{
for(y=0;y<n;y++)
{
fin>>q[x][y];
r[x][y]=q[x][y];//把目標(biāo)矩陣賦值給臨時(shí)矩陣
}
}
//算法分析與思路
min_count=m+n+1; //初始化變換次數(shù)為最壞情況
for(x=0;x<n;x++) //大循環(huán)開(kāi)始---枚舉源矩陣每一列變換為目標(biāo)矩陣每一列的情況，分別統(tǒng)計(jì)變換次數(shù)，取最少的那個(gè)。
{
for(a=0;a<m;a++)
for(b=0;b<n;b++)
q[a][b]=r[a][b]; //每枚舉一次都要將目標(biāo)矩陣恢復(fù)原狀。
count=0;
for(ii=0;ii<m;ii++)
{
temp=q[ii][0];
q[ii][0]=q[ii][x];//把目標(biāo)的每一列與第一列交換
q[ii][x]=temp;
}
if(0!=x)
count++;//如果有列轉(zhuǎn)換就執(zhí)行此句
for(a=0;a<m;a++)
{
if(p[a][0]!=q[a][0])//如果源矩陣不等于目標(biāo)矩陣
{
for(i3=0;i3<n;i3++)
{
if (q[a][i3]==0)
{
q[a][i3]=1; // 金幣翻轉(zhuǎn)行
}
else
{
q[a][i3]=0;
}
}
count++;//如果執(zhí)行if語(yǔ)句有金幣翻轉(zhuǎn)
}
} //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++;//目標(biāo)與源列對(duì)比有相等但列的位置不一樣執(zhí)行
match=true;
break;// 跳出1
}
}
if(!match)// 如果找不到兩列相等就執(zhí)行此語(yǔ)句
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>
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -