1195: Matrix
Description
给定两个n*m的矩阵A，B，每次只能对矩阵A做如下操作中的一种：
1.行交换：交换矩阵A中的任意两行。
2.列交换：交换矩阵A中的任意两列。
求解最少需要多少步(每做一次交换算一步)才能将矩阵A变成矩阵B。
Input
输入包含了多组测试数据。
每组数据格式如下：
第一行两个数n,m表示矩阵的行和列,其中n,m <= 16.
接下来的2到n+1行每行包含m个整数，表示矩阵A
紧接着的n+2到2n+1行中每行包含m个整数，表示矩阵B
输入保证矩阵中的元素都是小于等于n*m的，并且矩阵中没有相同元素。
Output
输出将矩阵A转换到矩阵B需要的最少操作数，如果不能将A转换到B，输入-1。
Sample Input
2 2 1 2 3 4 4 3 2 1 2 2 1 3 2 4 1 4 2 3
Sample Output
2 -1
解法：
暴力。
直接枚举每个数字的位置，然后交换到和最终位置相同的地方。若是该行/列已经不能交换，则输出-1；
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int be[20][20],en[20][20],tt[20][20];
int u1[20],u2[20];
int n,m;
void find1(int x,int &a,int &b)
{
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
if (tt[i][j]==x) {a=i;b=j;return;}
}
}
void find2(int x,int &a,int &b)
{
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
if (en[i][j]==x) {a=i;b=j;return;}
}
}
void change1(int a,int b)
{
int i,j,t;
for (i=1;i<=m;i++)
{
t=tt[a][i];
tt[a][i]=tt[b][i];
tt[b][i]=t;
}
}
void change2(int a,int b)
{
int i,j,t;
for (i=1;i<=n;i++)
{
t=tt[i][a];
tt[i][a]=tt[i][b];
tt[i][b]=t;
}
}
int main()
{
int i,j,a,b,c,d,xx,tot;
while (scanf("%d%d",&n,&m)!=EOF)
{
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{cin>>be[i][j];tt[i][j]=be[i][j];}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++) cin>>en[i][j];
memset(u1,0,sizeof(u1));
memset(u2,0,sizeof(u2));
xx=1;tot=0;
for (i=1;i<=n*m;i++)
{
find1(i,a,b);find2(i,c,d);
if (a!=c)
{
if (u1[a])
{xx=0;break;}
change1(a,c);
tot++;
}
u1[c]=1;
if (b!=d)
{
if (u2[b])
{xx=0;break;}
change2(b,d);
tot++;
}
u2[d]=1;
}
if (xx) cout<<tot<<endl;
else cout<<-1<<endl;
}
return 0;
}