BOI 2014 Portals

發表於 更新於 Disqus：

覺得這題還不錯，所以來寫題解。
以下內容都是出自寫這題時的想法，實作也是，所以不一定是最簡潔的作法(?)。

題目

題目敘述部份取自 luogu OJ，英文題敘可到 cses。

給定一個 $R\times C$ 的迷宮，每個格子都有一種方塊，迷宮四周也有 # 圍著：

  • # 墻，不可以走，不可以穿過
  • . 路，可以走
  • S 出生點，玩家從這里開始走，只有一個
  • C 終點，玩家要到達這里，只有一個

並且在任何時候，它都可以向上、左、下、右四個方向中的一個發射傳送門。當一個傳送門被發射，它會一直向發射的方向飛行，直到碰觸到墻壁。這時，傳送門會被放置在這堵墻上。
你可以走到相鄰一格，花費 $1$ 的時間，當迷宮有兩個傳送門時，也可以穿梭傳送門，需要 $1$ 的時間。

當迷宮內兩個傳送門時，你可以遠端的毀掉其中一個傳送門，此時你就可以再發射新的傳送門，毀掉一個傳送門不花費時間，發射傳送門也是。
求從出生點到終點最少需要多少時間。

Subtask 1, 2 (31 points): $R, C\le 50$

首先發現到：

當你穿梭過一個傳送門時，你可以直接毀掉那兩個傳送門。

假設你從傳送門 $A$ 到傳送門 $B$，你不可能再利用 $A$ 的傳送門，否則你一開始就不用傳送到 $B$。

當你之後還要利用 $B$ 的傳送門，可以當成再發射一個傳送門到 $B$ 的位置，因為發射傳送門不花費時間，所以這樣是等價的。

接下來再觀察一下，可以發現：

當你發射了第二個傳送門，你就要直接走到傳送門前傳送過去。

因為你不可能發射了第二個傳送門後到處亂晃再去搭傳送門(?)，而且：

你可以總是利用第二個傳送門到第一個傳送門。

因為如果你要搭第一個傳送門，那你肯定是去發射第二之後再回來搭第一個，這可以等價成先去射第二個再回來射第一個門。再來：

發射第二個傳送門後走過去，等價成先走過去然後發射第二個傳送門

所以你的策略一定是先發射第一個傳送門，晃一晃晃到了牆邊後原地發射第二個門，接著直接傳送過去第一個門。

因此你只要去紀錄第一個門的位置。
所以可以用以下狀態跑 BFS 最短路：
$$dis[x][y][a][b]\ := \text{ 人在 } (x, y)\text{ ，且第一個傳送門在 } (a, b)\text {的最短距離} $$

當 $(a, b) = (0, 0)$ 的時候代表場上沒有傳送門。

而你下一步可以走到上下左右，或者是往上下左右發射傳送門，或者當你在牆邊的時候可以傳送到第一個傳送門所在的位置並且毀掉那兩個傳送門。

但是要怎麼知道上下左右的第一個牆邊在哪裡？
可以預處理 dw, up, le, ri 代表下、上、左、右的第一個牆邊在哪裡。
轉移式為（這裡只列出 up，其餘可參考 code）。
$$ up[i][j] = \begin{cases} i & \text{if } arr[i - 1][j]\text{ is wall} \\ up[i-1][j] & \text{else} \end{cases}$$

預處理完你就能 $\mathcal{O}(1)$ 知道你下一步的位置了。

因為發射傳送門不用花費時間，所以這其實就是權重 0 跟 1 的最短路問題。
通用解法就是 0/1 BFS，作法是設個 deque，在走權重為 0 的邊時 push_front，否則 push_back，每次從 front 拿當前要走的點。
總時間複雜度 $\mathcal{O}((RC)^2)$。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
// 31/100
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const ll LINF = ll(2e18) + ll(1e15);
static auto LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();
 
const int N = 51;
int dis[N][N][N][N], up[N][N], dw[N][N], le[N][N], ri[N][N];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
 
signed main() {
	int n, m;
	cin >> n >> m;
	vector<string> arr(n + 2);
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[i] = '#' + arr[i];
		arr[i].push_back('#');
	}
	arr[0] = arr[n + 1] = string(m + 2, '#');
 
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] != '#') {
				if(arr[i][j - 1] == '#')
					le[i][j] = j;
				else
					le[i][j] = le[i][j - 1];
				if(arr[i - 1][j] == '#')
					up[i][j] = i;
				else
					up[i][j] = up[i - 1][j];
			}
		}
	}
	for(int i = n; i; i--) {
		for(int j = m; j; j--) {
			if(arr[i][j] != '#') {
				if(arr[i][j + 1] == '#')
					ri[i][j] = j;
				else
					ri[i][j] = ri[i][j + 1];
				if(arr[i + 1][j] == '#')
					dw[i][j] = i;
				else
					dw[i][j] = dw[i + 1][j];
			}
		}
	}
 
	memset(dis, 0x3f, sizeof dis);
 
	deque<tuple<int, int, int, int>> bfs;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] == 'S') {
				bfs.push_back({i, j, 0, 0});
				dis[i][j][0][0] = 0;
			}
		}
	}
	while(!bfs.empty()) {
		auto [x, y, a, b] = bfs.front();
		bfs.pop_front();
 
		if(dis[x][y][x][le[x][y]] > dis[x][y][a][b]) {
			dis[x][y][x][le[x][y]] = dis[x][y][a][b];
			bfs.push_front({x, y, x, le[x][y]});
		}
		if(dis[x][y][x][ri[x][y]] > dis[x][y][a][b]) {
			dis[x][y][x][ri[x][y]] = dis[x][y][a][b];
			bfs.push_front({x, y, x, ri[x][y]});
		}
		if(dis[x][y][up[x][y]][y] > dis[x][y][a][b]) {
			dis[x][y][up[x][y]][y] = dis[x][y][a][b];
			bfs.push_front({x, y, up[x][y], y});
		}
		if(dis[x][y][dw[x][y]][y] > dis[x][y][a][b]) {
			dis[x][y][dw[x][y]][y] = dis[x][y][a][b];
			bfs.push_front({x, y, dw[x][y], y});
		}
 
		bool ok = 0;
		for(int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
			if(arr[tx][ty] == '#')
				ok = true;
			else {
				if(dis[tx][ty][a][b] > dis[x][y][a][b] + 1) {
					dis[tx][ty][a][b] = dis[x][y][a][b] + 1;
					bfs.push_back({tx, ty, a, b});
				}
			}
		}
 
		if(ok && arr[a][b] != '#' && dis[a][b][0][0] > dis[x][y][a][b] + 1) {
			dis[a][b][0][0] = dis[x][y][a][b] + 1;
			bfs.push_back({a, b, 0, 0});
		}
 
	}
	int ans = INF;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] == 'C') {
				for(int a = 1; a <= n; a++)
					for(int b = 1; b <= m; b++)
						ans = min(ans, dis[i][j][a][b]);
			}
		}
	}
	cout << ans << '\n';
}

Subtask 3 (20 points): $R, C\le 200$，每個 . 周圍都有至少一個 #。

在這個子題中保證了你隨時能夠發射第二個傳送門並傳送到第一個傳送門（因為你隨時都在牆邊），並且注意到：

在發射第一個傳送門之後應該要立刻原地發射第二個傳送門傳送過去。

因為你亂晃亂晃然後才發射第二個走過去肯定不會比較好(?)
所以甚至不用紀錄第一個傳送門了，直接用 dis[x][y] 代表到那個位置的最短路，同時你可以做的事情有：

  1. 走到上下左右
  2. 往上下左右發射一個傳送門，同時原地弄個傳送門傳送過去

有了在上個子題的預處理，這些事情都能繼續 $\mathcal{O}(1)$ 做到。

時間複雜度 $\mathcal{O}(RC)$。

跟上個子題的作法聯集起來你就有了 51 分。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
// 51/100
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const ll LINF = ll(2e18) + ll(1e15);
static auto LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();
 
const int N = 51, N2 = 501;
int dis[N][N][N][N], up[N2][N2], dw[N2][N2], le[N2][N2], ri[N2][N2];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
vector<string> arr;
int n, m;
 
void solve() {
	vector<vector<int>> ans(n + 1, vector<int>(m + 1, INF));
	queue<pair<int, int>> bfs;
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= m; j++)
			if(arr[i][j] == 'S')
				ans[i][j] = 0, bfs.push({i, j});
	while(!bfs.empty()) {
		auto [x, y] = bfs.front();
		bfs.pop();
 
		auto w = ans[x][y] + 1;
 
		if(ans[x][le[x][y]] > w) {
			ans[x][le[x][y]] = w;
			bfs.push({x, le[x][y]});
		}
		if(ans[x][ri[x][y]] > w) {
			ans[x][ri[x][y]] = w;
			bfs.push({x, ri[x][y]});
		}
		if(ans[up[x][y]][y] > w) {
			ans[up[x][y]][y] = w;
			bfs.push({up[x][y], y});
		}
		if(ans[dw[x][y]][y] > w) {
			ans[dw[x][y]][y] = w;
			bfs.push({dw[x][y], y});
		}
 
		for(int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
			if(arr[tx][ty] == '#')
				continue;
			if(ans[tx][ty] > ans[x][y] + 1) {
				ans[tx][ty] = ans[x][y] + 1;
				bfs.push({tx, ty});
			}
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(arr[i][j] == 'C')
				cout << ans[i][j] << '\n';
}
 
signed main() {
	cin >> n >> m;
	arr.resize(n + 2);
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[i] = '#' + arr[i];
		arr[i].push_back('#');
	}
	arr[0] = arr[n + 1] = string(m + 2, '#');
 
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] != '#') {
				if(arr[i][j - 1] == '#')
					le[i][j] = j;
				else
					le[i][j] = le[i][j - 1];
				if(arr[i - 1][j] == '#')
					up[i][j] = i;
				else
					up[i][j] = up[i - 1][j];
			}
		}
	}
	for(int i = n; i; i--) {
		for(int j = m; j; j--) {
			if(arr[i][j] != '#') {
				if(arr[i][j + 1] == '#')
					ri[i][j] = j;
				else
					ri[i][j] = ri[i][j + 1];
				if(arr[i + 1][j] == '#')
					dw[i][j] = i;
				else
					dw[i][j] = dw[i + 1][j];
			}
		}
	}
	if(n > 50 || m > 50) {
		solve();
		return 0;
	}
 
	memset(dis, 0x3f, sizeof dis);
 
	deque<tuple<int, int, int, int>> bfs;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] == 'S') {
				bfs.push_back({i, j, 0, 0});
				dis[i][j][0][0] = 0;
			}
		}
	}
	while(!bfs.empty()) {
		auto [x, y, a, b] = bfs.front();
		bfs.pop_front();
		if(arr[x][y] == 'C')
			break;
 
		if(dis[x][y][x][le[x][y]] > dis[x][y][a][b]) {
			dis[x][y][x][le[x][y]] = dis[x][y][a][b];
			bfs.push_front({x, y, x, le[x][y]});
		}
		if(dis[x][y][x][ri[x][y]] > dis[x][y][a][b]) {
			dis[x][y][x][ri[x][y]] = dis[x][y][a][b];
			bfs.push_front({x, y, x, ri[x][y]});
		}
		if(dis[x][y][up[x][y]][y] > dis[x][y][a][b]) {
			dis[x][y][up[x][y]][y] = dis[x][y][a][b];
			bfs.push_front({x, y, up[x][y], y});
		}
		if(dis[x][y][dw[x][y]][y] > dis[x][y][a][b]) {
			dis[x][y][dw[x][y]][y] = dis[x][y][a][b];
			bfs.push_front({x, y, dw[x][y], y});
		}
 
		bool ok = 0;
		for(int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
			if(arr[tx][ty] == '#')
				ok = true;
			else {
				if(dis[tx][ty][a][b] > dis[x][y][a][b] + 1) {
					dis[tx][ty][a][b] = dis[x][y][a][b] + 1;
					bfs.push_back({tx, ty, a, b});
				}
			}
		}
 
		if(ok && arr[a][b] != '#' && dis[a][b][0][0] > dis[x][y][a][b] + 1) {
			dis[a][b][0][0] = dis[x][y][a][b] + 1;
			bfs.push_back({a, b, 0, 0});
		}
 
	}
	int ans = INF;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] == 'C') {
				for(int a = 0; a <= n; a++)
					for(int b = 0; b <= m; b++)
						ans = min(ans, dis[i][j][a][b]);
			}
		}
	}
	cout << ans << '\n';
}

Subtask 4, 5 (49 Points): $R, C\le 1000$

上個子題的作法在這子題會 WA 掉，為什麼？
因為上個子題中我們可以直接在射了第一個傳送門之後，原地發射第二個並且傳送過去。
然而這個子題並沒有保證所有點都是牆邊。
不過上個子題有個觀察：

在發射第一個傳送門之後應該要立刻原地發射第二個傳送門傳送過去。

上個子題可以原地發射第二個，那在這個子題呢？

在發射第一個傳送門之後應該盡可能快的走到牆邊，並且發射第二個傳送門傳送過去。

上個子題的觀察其實就是這個的特例，因為我們總是在牆邊所以不用想辦法進可能快的走到牆邊。

重新令 dis[x][y] 代表到那點的最短距離，現在我們能做的事情變成：

  1. 花費 $1$ 的時間走到上下左右
  2. 花費 $1$ 的時間射一個傳送門到上下左右第一個牆邊，並且花費 $mn[x][y]$ 的時間走到牆邊射第二個傳送門傳送過去。

現在的問題就是如何計算 mn？
其實 mn[x][y] 就是離 $(x, y)$ 最近的牆邊有多遠！

所以這就是多點源 BFS，起點是所有牆邊。
這樣就能花 $\mathcal{O}(RC)$ 預處理 mn。

我們要做的事情變成帶權的最短路了，所以就要使用 Dijkstra 演算法。
於是整體複雜度是 $\mathcal{O}(RClog(RC))$，並且滿分入手><。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// 100/100
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const ll LINF = ll(2e18) + ll(1e15);
static auto LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();
 
const int N = 1001;
int dis[N][N], up[N][N], dw[N][N], le[N][N], ri[N][N], mn[N][N];
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
 
signed main() {
	int n, m;
	cin >> n >> m;
	vector<string> arr(n + 2);
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		arr[i] = '#' + arr[i];
		arr[i].push_back('#');
	}
	arr[0] = arr[n + 1] = string(m + 2, '#');
 
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] != '#') {
				if(arr[i][j - 1] == '#')
					le[i][j] = j;
				else
					le[i][j] = le[i][j - 1];
				if(arr[i - 1][j] == '#')
					up[i][j] = i;
				else
					up[i][j] = up[i - 1][j];
			}
		}
	}
	for(int i = n; i; i--) {
		for(int j = m; j; j--) {
			if(arr[i][j] != '#') {
				if(arr[i][j + 1] == '#')
					ri[i][j] = j;
				else
					ri[i][j] = ri[i][j + 1];
				if(arr[i + 1][j] == '#')
					dw[i][j] = i;
				else
					dw[i][j] = dw[i + 1][j];
			}
		}
	}
 
	{
		memset(mn, 0x3f, sizeof mn);
		queue<pair<int, int>> bfs;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				if(le[i][j] == j || ri[i][j] == j || up[i][j] == i || dw[i][j] == i)
					mn[i][j] = 0, bfs.push({i, j});
		while(!bfs.empty()) {
			auto [a, b] = bfs.front();
			bfs.pop();
			for(int i = 0; i < 4; i++) {
				int x = a + dx[i], y = b + dy[i];
				if(arr[x][y] != '#' && mn[x][y] > mn[a][b] + 1) {
					mn[x][y] = mn[a][b] + 1;
					bfs.push({x, y});
				}
			}
		}
	}
 
	memset(dis, 0x3f, sizeof dis);
 
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> bfs;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(arr[i][j] == 'S') {
				bfs.push({0, i, j});
				dis[i][j] = 0;
			}
		}
	}
	while(!bfs.empty()) {
		auto [d, x, y] = bfs.top();
		bfs.pop();
		if(dis[x][y] > d)
			continue;
		if(arr[x][y] == 'C') {
			cout << d << '\n';
			break;
		}
 
		int g = dis[x][y] + mn[x][y] + 1;
		if(dis[x][le[x][y]] > g) {
			dis[x][le[x][y]] = g;
			bfs.push({g, x, le[x][y]});
		}
		if(dis[x][ri[x][y]] > g) {
			dis[x][ri[x][y]] = g;
			bfs.push({g, x, ri[x][y]});
		}
		if(dis[up[x][y]][y] > g) {
			dis[up[x][y]][y] = g;
			bfs.push({g, up[x][y], y});
		}
		if(dis[dw[x][y]][y] > g) {
			dis[dw[x][y]][y] = g;
			bfs.push({g, dw[x][y], y});
		}
 
		for(int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
			if(arr[tx][ty] != '#') {
				if(dis[tx][ty] > dis[x][y] + 1) {
					dis[tx][ty] = dis[x][y] + 1;
					bfs.push({dis[tx][ty], tx, ty});
				}
			}
		}
	}
}

結語

這題是我在 Virtual 時解出來的題目，但是我花了兩個小時才寫出來ww
其中花最久的時間就是想到只需要紀錄第一個傳送的位置，以及最後把子題 3 的觀察轉化成滿分解能夠使用的觀察。
這題充滿著各種經典的技巧與演算法，多點源 BFS、Dijkstra、計算上下左右時的 DP、0/1 BFS，以及滿滿的觀察！！
實作的部份看似很多，但其實沒有到很煩躁，畢竟要做的事情就是很清楚。