题意：
给出一个
n
∗
m
n*m
n∗m 的方格，每次交换一行或一列，问是否可以将该行还原回去，如果可以就输出最少操作数。（
a
a
a 为初始图形，
1
≤
n
,
m
≤
300
1\leq n,m\leq 300
1≤n,m≤300）
思路：
稍加分析，可以得出几个结论。还原操作数可以行列分开算。如果可以还原，则每行错位位置相同。
因此问题就变成了现在有一个数列，数列上有几个位置发生了错位，最少需要几步可以还原这个数列。
我们可以从小例子开始考虑，如果一串数字中有
2
2
2 个位置错位，最少需要几步？如果是
3
3
3 个位置、
4
4
4 个位置呢？
从上面的小例子分析中可以发现，错位关系，即
a
a
a 位置原本在
b
b
b 位置，
a
→
b
a\rightarrow b
a→b 关系。每个位置都有一个错位关系，最后这个错位关系会形成一个环。
例如排列
3
1
2
3 \ 1 \ 2
3 1 2，错位关系为
1
→
3
1\rightarrow 3
1→3、
2
→
1
2\rightarrow 1
2→1、
3
→
2
3\rightarrow 2
3→2 ，所有的错位关系最后形成了一个环，而还原这个环的步骤数为
n
−
1
n-1
n−1 ，
n
n
n 为这个环中的数字总数。由此，此题解决。
总结：
此题的收获主要是对于错位关系的分析，毫无头绪时先从小例子开始考虑，不断发现总结其中的共性，从而得到结论。
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
#define LOG3(x1,x2,y1,y2,z1,z2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << " , " << z1 << ": " << z2 << endl;
typedef long long ll
;
typedef double db
;
const int N
= 300+100;
const int M
= 1e5+100;
const db EPS
= 1e-9;
using namespace std
;
int n
,m
,mp
[N
][N
],vis
[N
],book
[N
*N
];
int check(){
rep(i
,1,n
){
rep(j
,1,m
) vis
[j
] = 0;
int base
= ((mp
[i
][1]-1)/m
)*m
;
rep(j
,1,m
){
int p
= mp
[i
][j
]-base
;
if(p
> m
|| p
< 1) return 0;
vis
[p
] = 1;
}
rep(j
,1,m
)
if(!vis
[j
]) return 0;
}
int base
= ((mp
[1][1]-1)/m
)*m
;
rep(j
,1,m
) vis
[j
] = mp
[1][j
]-base
;
rep(i
,1,n
){
int base
= ((mp
[i
][1]-1)/m
)*m
;
rep(j
,1,m
){
if(vis
[j
] != mp
[i
][j
]-base
) return 0;
}
}
rep(i
,1,n
) vis
[i
] = 0;
rep(i
,1,n
){
int base
= ((mp
[i
][1]-1)/m
)+1;
if(base
> n
|| base
< 1) return 0;
vis
[base
] = 1;
}
rep(i
,1,n
)
if(!vis
[i
]) return 0;
rep(i
,1,n
)
rep(j
,1,m
) book
[mp
[i
][j
]] = 1;
rep(i
,1,n
*m
)
if(book
[i
] != 1) return 0;
return 1;
}
int main()
{
scanf("%d%d",&n
,&m
);
rep(i
,1,n
)
rep(j
,1,m
) scanf("%d",&mp
[i
][j
]);
if(check()){
int ans
= 0;
rep(i
,1,n
){
vis
[i
] = ((mp
[i
][1]-1)/m
)+1;
}
rep(i
,1,n
){
if(vis
[i
] == i
) continue;
else{
int tp
= vis
[i
];
while(tp
!= i
){
int xx
= tp
;
tp
= vis
[tp
]; ans
++;
vis
[xx
] = xx
;
}
}
}
rep(j
,1,m
){
vis
[j
] = mp
[1][j
]%m
;
if(vis
[j
] == 0) vis
[j
] = m
;
}
rep(i
,1,m
){
if(vis
[i
] == i
) continue;
else{
int tp
= vis
[i
];
while(tp
!= i
){
int xx
= tp
;
tp
= vis
[tp
]; ans
++;
vis
[xx
] = xx
;
}
}
}
printf("%d\n",ans
);
}
else printf("*\n");
return 0;
}
