赛时这道题卡了一段时间，赛时代码如下：
#include<bits/stdc++.h>
using namespace std;
int ans,h;
int a[505][505];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]==min(i,j))ans++;
}
if(ans==n*m){
cout<<ans;
return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]>=1&&a[i][j]<=min(n,m)){
int t=a[i][j],c=min(i,j),v=a[t][t];
//要想成为不动点，可以换到(t,t)~(t,m) or (t,t)~(n,t)
//换过来成为不动点，要求值满足v==c
if(i!=t||j!=t){
if(v==c&&v==t)h=max(h,1);
else if(v==c&&v!=t)h=2;
else if(v!=c&&v!=t)h=max(h,1);
else if(v!=c&&v==t)h=max(h,0);
}
for(int k=t+1;k<=m;k++){
if(i!=t||j!=k){
v=a[t][k];
if(v==c&&v==t)h=max(h,1);
else if(v==c&&v!=t)h=2;
else if(v!=c&&v!=t)h=max(h,1);
else if(v!=c&&v==t)h=max(h,0);
}
}
for(int k=t+1;k<=n;k++){
if(i!=k||j!=t){
v=a[k][t];
if(v==c&&v==t)h=max(h,1);
else if(v==c&&v!=t)h=2;
else if(v!=c&&v!=t)h=max(h,1);
else if(v!=c&&v==t)h=max(h,0);
}
}
}
}
}
cout<<min(ans+h,n*m);
return 0;
}
上面这张图，以10✕7矩阵为例，表示每个点要是不动点需要的值。
我们考虑一下所有增加不动点数量的交换方式。
初步思考，可能增加不动点数量的交换无非三种情况：
- 两个非不动点->一个不动点，一个非不动点 不动点数+1
- 两个非不动点->两个不动点 不动点数+2
- 一个不动点，一个非不动点->两个不动点 不动点数+1
第一种情况如下图：
第二种情况如下图：
如果遇到第二种情况，可以直接断定这就是最优方案，不用再继续下去了。
第三种情况，我们细想一下，两个位置如果在“同一色块”，明显不成立，那么两个位置只能在“不同色块”，但是，这样也不成立，因为之前的不动点必然会变成非不动点，故这种情况并不存在。
也就是说，我们总共只有两种可能：
- 两个非不动点->一个不动点，一个非不动点 不动点数+1
- 两个非不动点->两个不动点 不动点数+2
现在我们再仔细讨论一下这种情况的代码具体实现思路。
等一下，先到这里，我要去思考一下了。
好了，我又回来了。首先，两种情况讨论的都是非不动点，我们需要一个高效的结构去存储非不动点的信息。
就拿示例2来说吧。
我改了一下代码，通过了88.89%。
#include<bits/stdc++.h>
using namespace std;
int ans,h;
int a[505][505];
set<int> v[505];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]==min(i,j))ans++;
else v[min(i,j)].insert(a[i][j]);
}
for(int i=1;i<=min(n,m);i++){
for(int e:v[i]){
if(v[e].count(i)){
h=2;
break;
}
else h=1;
}
if(h==2)break;
}
cout<<ans+h;
return 0;
}刚又调了一下，终于过了！
#include<bits/stdc++.h>
using namespace std;
int ans,h;
int a[505][505];
set<int> v[505];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]==min(i,j))ans++;
else v[min(i,j)].insert(a[i][j]);
}
for(int i=1;i<=min(n,m);i++){
for(int e:v[i]){
if(v[e].count(i)){
h=2;
break;
}
else if(v[e].size())h=1;
}
if(h==2)break;
}
cout<<ans+h;
return 0;
}