Codeforces 677D Vanya and Treasure

链接

传送门

题意

给出$n \times m$的矩阵,每个矩阵中的数字都在$[1,p]$,保证每个数字出现至少一次,$p$只出现1次。从$(1,1)$出发,依次经过含有$1$到$p$,求最短路。

思路

设$(i,j)$包含的数字为$x$,一个显然的状态$dp[i][j]$表示经过了前$x$个数之后到$(i,j)$点的最短路,可以从所有包含$x-1$的格子转移过来。设包含$x$的格子数为$cnt[x]$,每次转移的操作数为$cnt[x]cnt[x-1]$。但是直接这么做的复杂度最坏情况下达到了$O(n^2m^2)$并不能过。

所以我们加入暴力的方法,当$cnt[x]cnt[x-1]>n*m$时,直接用所有包含$x-1$的个子作为起点bfs,单次转移复杂度为$O(nm)$。

可以证明,最终复杂度为$O(nm\sqrt{nm})$。

复杂度证明:Codeforces Round #355 (Div. 2) Editorial

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
#include <map>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxn = 305;
int d[maxn][maxn], dp[maxn][maxn];
queue<pii> q;
vector<pii> v[maxn * maxn];
int dis(const pii& a, const pii& b) {
return abs(a.X - b.X) + abs(a.Y - b.Y);
}
void Set(int& a, int b) {
if (a > b) {
a = b;
}
}
bool cmp(const pii& p1, const pii& p2) {
return dp[p1.X][p1.Y] < dp[p2.X][p2.Y];
}
int main() {
int n, m, p, x;
scanf("%d%d%d", &n, &m, &p);
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &x);
v[x].push_back(make_pair(i, j));
if (x == 1) {
dp[i][j] = i + j - 2;
}
}
}
for (int i = 2; i <= p; ++i) {
if (v[i - 1].size() * v[i].size() <= n * m) {
for (pii& p1: v[i - 1]) {
for (pii& p2: v[i]) {
Set(dp[p2.X][p2.Y], dp[p1.X][p1.Y] + dis(p1, p2));
}
}
} else {
memset(d, -1, sizeof d);
for (pii& p: v[i - 1]) {
d[p.X][p.Y] = dp[p.X][p.Y];
}
sort(v[i - 1].begin(), v[i - 1].end(), cmp);
x = 1;
q.push(v[i - 1][0]);
while (!q.empty()) {
pii k = q.front();
q.pop();
while (x < v[i - 1].size() && dp[v[i - 1][x].X][v[i - 1][x].Y] <= d[k.X][k.Y]) {
q.push(v[i - 1][x++]);
}
for (int j = 0; j < 4; ++j) {
int a = k.X + dx[j], b = k.Y + dy[j];
if (a >= 1 && a <= n && b >= 1 && b <= m && d[a][b] == -1) {
d[a][b] = d[k.X][k.Y] + 1;
q.push(make_pair(a, b));
}
}
if (q.empty() && x < v[i - 1].size()) {
q.push(v[i - 1][x++]);
}
}
for (pii& p: v[i]) {
dp[p.X][p.Y] = d[p.X][p.Y];
}
}
}
printf("%d\n", dp[v[p][0].X][v[p][0].Y]);
return 0;
}