本文共 2269 字，大约阅读时间需要 7 分钟。
被坑了，一开始以为如果有一行已经是排好序了，然后有一行需要转换的次数 >= 2的话，那就直接no了。
因为一开始以后转换次数>=2必定需要用了转换列，然后就搞乱了排序好的哪一行，但是排序好的那一行可以用交换两个数来修复。
2 4
1 2 3 4
2 1 4 3
然后其他的思路就是，①、有一个需要转换3次以上的就不行了。
②、随便找一个转换次数为2的，开始暴力枚举他们两两用列转换，然后再判断是否全部只需要一次转换就行了。
#include #include #include #include #include using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include const int maxn = 20 + 20;int a[maxn][maxn];int n, m;int mx;bool check() { bool flag = false; for (int i = 1; i <= n; ++i) { int j; for (j = 1; j <= m; ++j) { if (a[i][j] != j) { break; } } if (j == m + 1) { flag = true; break; } } if (flag == false) return false; for (int i = 1; i <= n; ++i) { int t = 0; for (int j = 1; j <= m; ++j) { if (a[i][j] != j) ++t; }// if (t >= 3) return true; mx = max(t, mx); } if (mx >= 5) return true; return false;}int row[maxn];void getrow() { for (int i = 1; i <= n; ++i) { row[i] = 0; for (int j = 1; j <= m; ++j) { row[i] += a[i][j] != j; } }}bool allone() { for (int i = 1; i <= n; ++i) { if (row[i] >= 3) return false; } return true;}int gg[maxn];void get(int aa, int bb) { for (int i = 1; i <= n; ++i) { swap(a[i][aa], a[i][bb]); }}void show() { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cout << a[i][j] << " "; } cout << endl; } cout << endl;}void work() { cin >> n >> m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin >> a[i][j]; } } if (check() || mx >= 5) { cout << "NO" << endl; return; } getrow(); if (allone()) { cout << "YES" << endl; return; } int pos;// show(); for (int i = 1; i <= n; ++i) { if (row[i] >= 3) { pos = i; break; } } int lengg = 0; for (int i = 1; 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 = 1; i <= lengg; ++i) { for (int j = i + 1; 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 0;}
转载于:https://www.cnblogs.com/liuweimingcprogram/p/5940681.html
