题目描述

难度分:$2600$

输入$n$、$m(1 \leq n \times m \leq 4 \times 10^5)$和$n$行$m$列的网格图，元素范围$[1,n \times m]$。保证范围中的每个数都恰好出现一次。

你从值为$1$的格子出发。每一步，只能走上下左右相邻的格子。你可以重复访问同一个格子。

目标：访问所有格子，并满足，如果$x \lt y$，那么访问元素值$x$的时间必须早于访问元素值$y$的时间。

你可以通过交换两个任意位置的格子（无需相邻）来实现目标。输出最小交换次数，具体如下：

• 如果不用交换，输出$0$。
• 如果至少要交换$2$次，输出$2$。
• 如果只需交换$1$次，输出$1$，以及方案数。

输入样例$1$

3 3
2 1 3
6 7 4
9 8 5

输出样例$1$

0

输入样例$2$

2 3
1 6 4
3 2 5

输出样例$2$

1 3

输入样例$3$

1 6
1 6 5 4 3 2

输出样例$3$

2

算法

构造

真的难，根本没有思路。

定义好格子为：要么是$1$，要么至少有一个小于自己的邻居。若不满足，则为坏格子。

观察：如果所有格子都是好格子，那么无需交换。

证明：反证法。假设从$1$开始，某个时刻怎么走也走不下去了（遇到了一堵墙）。设此时没有被访问的最小元素为$x$，那么$x$必然在墙的另一侧。由于所有比$x$小的数我们都访问过了，所以$x$的邻居必然都大于$x$，所以$x$必然是个坏格子，矛盾，故原命题成立。

我们可以通过交换坏格子（或者坏格子的邻居）与其他的格子，来让坏格子变成好格子。

如果存在坏格子，我们只需考察其中一个坏格子和它的$4$个邻居，因为这个坏格子必须变成好格子。

枚举其中一个坏格子及其邻居，记作$(x,y)$，以及枚举所有$(i,j)$（$i \in [0,n)$，$j \in [0,m)$），交换二者。交换后，检查是否有坏格子仍然是坏格子，如果是，那么交换失败。如果不是，继续判断$(x,y)$，$(i,j)$及其邻居（至多$10$个格子）是否均为好格子。如果是，那么将这两个格子的位置$((x,y),(i,j))$加入到集合$st$中（目的是去重，注意保证坐标字典序小的在前面）。

如果枚举结束后，$st$是空的，说明至少要操作$2$次；否则只需操作$1$次，且方案数为$st$的大小。

复杂度分析

时间复杂度

找出所有的坏格子需要遍历$O(nm)$个格子，检查每个格子$(i,j)$是否是好格子需要遍历它的$4$个邻居，因此时间复杂度还是$O(nm)$。

挑出一个坏格子，遍历它的$4$个邻居和自己。对每个$(x,y)$，需要检查$O(nm)$个格子与它交换是不是有效交换，时间复杂度仍然是$O(nm)$。但是将交换方案存入有序集合的时间复杂度是$log$级别，有序集合在最差情况下也会存$O(nm)$级别的方案，所以整个算法的时间复杂度$O(nmlog_2{nm})$。

空间复杂度

空间消耗主要是存储交换方案的有序集合，在最差情况下会存$O(nm)$个元素，所以整个算法的额外空间复杂度为$O(nm)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int n, m;
const int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};

int main() {
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    function<bool(int, int)> ok = [&](int i, int j) {
        return a[i][j] == 1 ||
               (j > 0 && a[i][j - 1] < a[i][j]) ||
               (j + 1 < m && a[i][j + 1] < a[i][j]) ||
               (i > 0 && a[i - 1][j] < a[i][j]) ||
               (i + 1 < n && a[i + 1][j] < a[i][j]);
    };
    function<bool(int, int)> ok2 = [&](int i, int j) {
        return ok(i, j) &&
               (j == 0 || ok(i, j - 1)) &&
               (j + 1 == m || ok(i, j + 1)) &&
               (i == 0 || ok(i - 1, j)) &&
               (i + 1 == n || ok(i + 1, j));
    };
    vector<array<int, 2>> badpos;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(!ok(i, j)) {
                badpos.push_back({i, j});
            }
        }
    }
    if(badpos.empty()) {
        puts("0");
        return 0;
    }
    set<array<int, 2>> st;
    int x = badpos[0][0], y = badpos[0][1];
    for(int k = 0; k < 5; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                swap(a[nx][ny], a[i][j]);
                bool valid = true;
                for(auto& q : badpos) {
                    if(!ok(q[0], q[1])) {
                        valid = false;
                        goto next;
                    }
                }
                if(valid && ok2(nx, ny) && ok2(i, j)) {
                    st.insert({min(nx*m + ny, i*m + j), max(nx*m + ny, i*m + j)});
                }
            next:
                swap(a[nx][ny], a[i][j]);
            }
        }
    }
    if(st.empty()) {
        puts("2");
    }else {
        printf("1 %d\n", (int)st.size());
    }
    return 0;
}