题目描述
难度分:2600
输入n、m(1≤n×m≤4×105)和n行m列的网格图,元素范围[1,n×m]。保证范围中的每个数都恰好出现一次。
你从值为1的格子出发。每一步,只能走上下左右相邻的格子。你可以重复访问同一个格子。
目标:访问所有格子,并满足,如果x<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∈[0,n),j∈[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(nmlog2nm)。
空间复杂度
空间消耗主要是存储交换方案的有序集合,在最差情况下会存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;
}