http://codeforces.com/contest/724/problem/B
被坑了,一开始以为如果有一行已经是排好序了,然后有一行需要转换的次数 >= 2的话,那就直接no了。
因为一开始以后转换次数>=2必定需要用了转换列,然后就搞乱了排序好的哪一行,但是排序好的那一行可以用交换两个数来修复。
2 4
1 2 3 4
2 1 4 3
然后其他的思路就是,①、有一个需要转换3次以上的就不行了。
②、随便找一个转换次数为2的,开始暴力枚举他们两两用列转换,然后再判断是否全部只需要一次转换就行了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
int a[maxn][maxn];
int n, m;
int mx;
bool check() {
bool flag = false;
for (int i = ; i <= n; ++i) {
int j;
for (j = ; j <= m; ++j) {
if (a[i][j] != j) {
break;
}
}
if (j == m + ) {
flag = true;
break;
}
}
if (flag == false) return false;
for (int i = ; i <= n; ++i) {
int t = ;
for (int j = ; j <= m; ++j) {
if (a[i][j] != j) ++t;
}
// if (t >= 3) return true;
mx = max(t, mx);
}
if (mx >= ) return true;
return false;
}
int row[maxn];
void getrow() {
for (int i = ; i <= n; ++i) {
row[i] = ;
for (int j = ; j <= m; ++j) {
row[i] += a[i][j] != j;
}
}
}
bool allone() {
for (int i = ; i <= n; ++i) {
if (row[i] >= ) return false;
}
return true;
}
int gg[maxn];
void get(int aa, int bb) {
for (int i = ; i <= n; ++i) {
swap(a[i][aa], a[i][bb]);
}
}
void show() {
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
void work() {
cin >> n >> m;
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
cin >> a[i][j];
}
} if (check() || mx >= ) {
cout << "NO" << endl;
return;
}
getrow();
if (allone()) {
cout << "YES" << endl;
return;
}
int pos;
// show();
for (int i = ; i <= n; ++i) {
if (row[i] >= ) {
pos = i;
break;
}
}
int lengg = ;
for (int i = ; i <= m; ++i) {
if (a[pos][i] != i) {
gg[++lengg] = i;
}
}
// for (int i = 1; i <= m; ++i) {
// cout << gg[i] << " ";
// }
// cout << endl;
for (int i = ; i <= lengg; ++i) {
for (int j = i + ; j <= lengg; ++j) {
get(gg[i], gg[j]);
getrow();
if (allone()) {
cout << "YES" << endl;
return;
}
get(gg[i], gg[j]);
}
}
cout << "NO" << endl;
return;
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}