跳转至

交互題

上個世紀的 IOI 就已涉及交互題。雖然交互題近年來沒有在省選以下的比賽中出現，不過 2019 年裏 NOI 系列比賽中連續出現《P5208[WC2019]I 君的商店》、《P5473[NOI2019]I 君的探險》兩道交互題，這可能代表着交互題重新回到 NOI 系列比賽中。

交互題沒有很高的前置算法要求，一般也沒有嚴格的時間限制，程序的優秀程度往往僅取決於交互次數限制。所以學習交互題時，建議按照難度循序漸進。要是有意鍛鍊算法思維而不只是單純地學習算法，那麼完成交互題是很不錯的方法。雖然交互題對選手已掌握算法的要求通常較低，但仍建議掌握一定提高和省選算法後再嘗試做交互題，因為此時自己的算法思維水平和知識面已經達到了一定水平。基礎的交互題介紹可以參考 OI Wiki 的 題型介紹 - 交互題。

交互題的特殊錯誤：

  • 選手每一次輸出後都需要刷新緩衝區，否則會引起 Idleness limit exceeded 錯誤。另外，如果題目含多組數據並且程序可以在未讀入所有數據前就知道答案，也仍然要讀入所有數據，否則同樣會因為讀入混亂引起 ILE（可以一次提出多次詢問，一次接收所有詢問的回答）。同時儘量不要使用快讀。
  • 如果程序查詢次數過多，則在 Codeforces 上會給出 Wrong Answer 的評測結果（不過評測系統會説明 Wrong Answer 的原因），而 UVa 會給出 Protocol Limit Exceeded (PLE) 的評測結果。
  • 如果程序交互格式錯誤，UVa 會給出 Protocol Violation (PV) 的評測結果。

由於交互題輸入輸出較為繁瑣，所以建議分別封裝輸入和輸出函數。

比賽時如果出題人給出了 grader 頭文件（用於 grader 交互題的調試）或者 checker 程序（用於 stdio 交互題的調試），則交互題的調試比較簡單，因為交互題的對拍會比普通題目的對拍困難很多。沒有 testlib.h 的情況下。交互細節較多的題目的 stdio 交互庫會一般有 3k 代碼量，再加上 3k 長度的對拍器，至少需要一小時實現。但是，無論是否有調試程序，調試交互題的代碼都往往需要選手模擬與程序的交互過程，因此交互題需要選手能設計出高質量的程序，儘量保證一遍做對，同時擁有較強的靜態查錯能力。

例題：

CF679A Bear and Prime 100

每個質數都有且只有兩個因數，所以直接枚舉要猜的數的因數。由於限制最多詢問 20 次，並且對於較大的數（如 92）嘗試分解質因數時發現需要最多枚舉到 \(\lfloor\frac{n}{2}\rfloor\) 的質數。所以我們先篩出 50 以內的質數，每次把所有這些數都詢問一遍。

由於本題對拍比較容易，可以直接把值域內的數都嘗試一遍。我們會發現程序無法有效處理質數的平方。所以我們要把 2,3,5,7 的平方 4,9,25,49 都放進去，總共 19 個數字，符合題意。

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <cstdio>
const int prime[] = {2,  3,  4,  5,  7,  9,  11, 13, 17, 19,
                     23, 25, 29, 31, 37, 41, 43, 47, 49};
int cnt = 0;
char res[5];

int main() {
  for (int i : prime) {
    printf("%d\n", i);
    fflush(stdout);
    scanf("%s", res);
    if (res[0] == 'y' && ++cnt == 2) return printf("composite"), 0;
  }
  printf("prime");
  return 0;
}

CF843B Interactive LowerBound

鏈表最多有 \(5 \times 10 ^ 4\) 個元素，但我們只能詢問 \(1999\) 次，並且只能獲取元素的後一個元素，所以普通的遍歷整個鏈表的方法不可用。直接設法逼近目標元素的位置只有一種方法：隨機撒點。

對於 \(n < 2000\) 的情況直接枚舉，\(n \ge 2000\) 時，我們直接撒 1000 個點，這時這些點之間的期望距離很小，我們可以直接從小於 \(x\) 的最大值開始向後遍歷，可以證明在到達下一個點之前我們就已得到答案。遍歷的過程中一旦找到大於等於 \(x\) 的元素，就可以直接推出。

雖然整體思路簡單，但實際情況下，如果沒有學習過模擬退火等非完美隨機算法，思考起來很可能會困難一些。

同時由於 Codeforces 具有 hack 機制，很多人會刻意卡掉沒有初始化隨機種子的代碼，所以在 random_shuffle() 函數前需要 srand((size_t)new char)。

參考代碼 
 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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
const int N = 50005;
int n, start, x;
int a[N];

int main() {
  scanf("%d%d%d", &n, &start, &x);
  if (n < 2000) {
    int ans = 2e9;
    for (int i = 1; i <= n; i++) {
      printf("? %d\n", i), fflush(stdout);
      int val, next;
      scanf("%d%d", &val, &next);
      if (val >= x) ans = std::min(ans, val);
    }
    if (ans == 2e9) ans = -1;
    printf("! %d", ans), fflush(stdout);
  } else {
    srand((size_t) new char);
    int p = start, ans = 0;
    for (int i = 1; i <= n; i++) a[i] = i;
    std::random_shuffle(a + 1, a + n + 1);
    for (int i = 1; i <= 1000; i++) {
      printf("? %d\n", a[i]), fflush(stdout);
      int val, next;
      scanf("%d%d", &val, &next);
      if (val < x && val > ans) p = a[i], ans = val;
    }
    while (p != -1 && ans < x) {
      printf("? %d\n", p), fflush(stdout);
      int val, next;
      scanf("%d%d", &val, &next);
      ans = val;
      p = next;
    }
    if (ans < x) ans = -1;
    printf("! %d", ans), fflush(stdout);
  }
  return 0;
}

UOJ206[APIO2016]Gap

分兩個子任務討論：

  1. 查詢次數限制。

    我們考慮第一次查詢。因為我們一開始不知道任何數，所以我們需要詢問範圍 \([1, 10 ^ {18}]\)，獲得最大最小值。

    由於查詢次數限制剛好為 \(\frac{N + 1}{2}\)，所以考慮怎麼每一次都能獲取之前沒有獲取過的值，這樣能大概在次數範圍內獲取序列內的所有數。方法也很簡單：每次查詢 \([s, t]\) 後，設獲得的值為 \(mn, mx\)，則下一次查詢 \([mn + 1, mx - 1]\)。

  2. 詢問區間大小限制。

    由於題目要求詢問區間內的數的數量之和不能超過 \(3N\)，所以考慮最小化詢問區間。上面的方法不再可用，因為其詢問區間內的數數量之和規模為 \(O(N ^ 2)\)。我們可以考慮二分值域，但這種方法並不可靠，最壞可能會被卡到 \(O(N ^ 2)\)。所以我們需要更有效的劃分值域的方法，避免查詢區間內的點重複查詢，浪費機會。

    考慮到答案不會小於 \(\lfloor\frac{a_n - a_1}{N - 1}\rfloor\)，所以我們可以考慮按這個值劃分值域，設 \(i\) 初始為 0，\(ans\) 初始為上述值，每次詢問 \([i, i + ans]\) 並且更新 \(ans\)，之後再以 \(ans\) 為步長讓 \(i\) 自增。

    不過這種方法也不能很好地適用於子任務 1，因為最壞可能很多詢問的值域內一個數都沒有。

參考代碼 
 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
#include <algorithm>
#include <cstdio>

#include "gap.h"

long long findGap(int T, int N) {
  static long long a[100005] = {}, ans = 0;
  long long s = 0, t = 1e18, s1, t1;
  if (T == 1) {
    int l = 1, r = N;
    while (l <= r) {
      MinMax(s, t, &s1, &t1);
      a[l++] = s1, a[r--] = t1;
      s = s1 + 1, t = t1 - 1;
    }
    for (int i = 2; i <= N; i++) ans = std::max(ans, a[i] - a[i - 1]);
  } else if (T == 2) {
    MinMax(s, t, &s1, &t1);
    ans = (t1 - s1) / (N - 1);
    long long l = s1 + 1, r = t1, last = s1;
    for (long long i = l; i <= r;) {
      MinMax(i, i + ans, &s1, &t1);
      i += ans + 1;
      if (s1 != -1) ans = std::max(ans, s1 - last), last = t1;
    }
  }
  return ans;
}

CF750F New Year and Finding Roots

看到 \(h \le 7\)，詢問次數 \(\le 16\) 的嚴格要求，我們需要非常嚴格地最大化利用訪問獲得的信息。

\(h \le 4\) 時可以直接暴力枚舉。然而 \(h > 4\) 時需要很高效的遍歷算法。

隨機撒點不是好方法，因為隨機撒點無法確定自己是否足夠接近根節點了，並且單純隨機撒點，至少有一次碰到根節點的概率為 \(1 - (\frac{2 ^ h - 2}{2 ^ h - 1})\)，即使排除重複撒點的情況後，碰到根節點的概率仍然非常小。

由於 \(1 \le k \le 3\)，並且我們並不知道哪一邊更接近根節點，所以我們考慮最壞的情況，即如果 \(k = 3\) 時，前兩次我們的遍歷方向都是遠離根節點的，第三次遍歷方向是接近根節點的。所以我們必須往三個方向都遍歷。

考慮 bfs 和 dfs 兩種遍歷方法。由於 bfs 搜索樹可能很大，所以我們優先考慮 dfs。當然，如果我們知道當前的深度，並且當前深度小到深度範圍內的搜索樹規模小於等於剩餘次數，我們就可以直接 bfs。

知道當前節點的深度，以及當前遍歷的方向會獲得很大優勢。然而知道當前在往根節點還是在往葉子節點遍歷是非常困難的事情。如果使用 dfs，只有當遍歷到根節點（\(k = 2\)）或者葉子節點（\(k = 1\)）時才知道當前方向。所以我們需要儘可能知道當前節點深度，並且不能採用類似迭代加深搜索的方法，遍歷中途停下來。

考慮隨機一個初始節點，從初始節點出發可能碰到上面的最壞情況。

如果 \(k = 1\)，我們就可以直接知道當前節點的深度。

如果 \(k = 2\)，那當前節點即根節點。

如果 \(k = 3\)，我們直接考慮往三個方向 dfs。考慮到其中兩個方向是直接往葉子節點的方向，遍歷路徑長度相同；另一個方向是往根節點的方向，不過可能中途不小心往葉子節點的方向走了，遍歷路徑長度會較大。此時我們就可以計算出當前節點的深度。

當 \(k = 1\) 或者 \(k = 3\) 時，我們需要考慮較長的遍歷路徑。我們可以知道路徑上深度最小的點（必定比初始節點深度小）。如果我們為訪問過的節點打標記，不再遍歷，此時從該節點開始就只有一條遍歷路徑。雖然這條路徑可能還是會走向葉子節點，但是這條路徑上同樣必然存在深度比起點小的節點，我們就可以從這個節點開始繼續重複上面的步驟。

當然，我們考慮 \(h = 7\) 的最壞情況時（每次只往根節點走一步，就直接往葉子節點走），會發現如果只 dfs，最壞需要 \(\frac{(1 + 7) \times 7}{2} = 28\) 次詢問。不過我們已經知道初始節點的深度，所以我們可以算出所有已遍歷節點的深度，並且根據我們開始時對 bfs 的討論，判斷是否可以從深度最小的點直接 bfs。

這時，我們可以算出最壞需要 17 次。所以我們考慮從搜索樹上去掉一個節點（根據 dfs 只能盲目遍歷的性質，我們考慮 bfs）：即當進行深度為 \(k\) 的 bfs 時，搜索樹節點最壞有 \(2 ^ k - 1\) 個，可能需要 \(2 ^ k - 1\) 次詢問才能確定哪個節點的鄰居恰有 2 個。不過我們如果已經對其中 \(2 ^ k - 2\) 個節點詢問後，可以知道最後一個節點肯定是根節點。

此時最壞情況下的最優解為：\(h = 7\) 時，從葉子節點 dfs，每次都是隻往根節點走一步，就直接往葉子節點走，詢問 10 次後，當前已知最小深度的節點深度為 4，由於已知其父親，直接從其父親開始 bfs（搜索樹深度為 3，節點數為 \(2 ^ 3 - 1 = 7\)）。在 bfs 時詢問了 \(2 ^ 3 - 2 = 6\) 次後，確定 bfs 搜索樹上最後一個節點為根節點。

此時我們的算法可以剛好卡到最壞 16 次。

參考代碼 
 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
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int N = 256 + 5;
int T, h, chance;
bool ok;
vector<int> to[N], path;

bool read(int x) {
  if (to[x].empty()) {
    printf("? %d\n", x), fflush(stdout);
    int k, t;
    scanf("%d", &k);
    if (k == 0) exit(0);
    for (int i = 0; i < k; i++) {
      scanf("%d", &t);
      to[x].push_back(t);
    }
    if (k == 2) {
      printf("! %d\n", x), fflush(stdout);
      return ok = true;
    }
    chance--;
  }
  return false;
}

bool dfs(int x) {
  if (to[x].empty()) path.push_back(x);
  if (read(x)) return true;
  for (int i : to[x])
    if (to[i].empty()) return dfs(i);
  return false;
}

void bfs(int s, int k) {
  queue<int> q;
  for (int i : to[s])
    if (to[i].empty()) q.push(i);
  for (int i = 1; i < k; i++) {
    int x = q.front();
    q.pop();
    if (read(x)) return;
    for (int j : to[x])
      if (to[j].empty()) q.push(j);
  }
  for (int i = 1; i < k; i++) {
    int x = q.front();
    q.pop();
    if (read(x)) return;
  }
  printf("! %d\n", q.front()), fflush(stdout);
}

int main() {
  for (scanf("%d", &T); T--;) {
    ok = false;
    for (int i = 0; i < N; i++) to[i].clear();
    chance = 16;
    scanf("%d", &h);
    if (h == 0) exit(0);
    vector<int> long_path;
    if (read(1)) continue;
    int root, dep;
    if (to[1].size() == 1)
      root = 1, dep = h;
    else {
      for (int i : to[1]) {
        path.clear();
        if (dfs(i)) break;
        if (path.size() > long_path.size()) swap(path, long_path);
      }
      if (ok) continue;
      dep = h - (path.size() + long_path.size()) / 2;
      root = long_path.at((long_path.size() - (h - dep)) - 1);
    }
    while ((1 << (dep - 1)) - 2 > chance) {
      path.clear();
      if (dfs(root)) break;
      dep = h - (h - dep + path.size()) / 2;
      root = path.at((path.size() - (h - dep)) - 1);
    }
    if (ok == false) bfs(root, 1 << (dep - 2));
  }
  return 0;
}

UVa12731 太空站之謎 Mysterious Space Station

由於唯一的反饋是移動時是否撞牆，所以我們應該考慮在機器人不走丟的情況下，儘量接近牆邊走路，這樣有幾個好處：

  • 靠近牆邊走路時，很容易知道自己會不會撞牆，獲取到儘量多的信息。
  • 牆邊都是不會出現傳送門的格子，可以避免機器人走丟。

所以，我們如果已知機器人可能在牆邊的某個位置，要確定機器人是不是真的在這個位置，就可以通過 「單手扶牆法」 確定自己是不是真的在這個位置。根據拓撲學原理，在兩邊都是牆的迷宮中，如果從入口進入，並且總是用一隻手扶着同一邊牆，就可以保證找到出口。由於本題中的牆是閉合的，所以只需要沿着牆邊的道路走，就可以保證可以回到原點而不會撞牆。另外，由於牆邊的道路是地圖上的最大閉合迴路，所以實際代碼中並不需要特意撞牆以保證機器人在牆邊，可以使用標記在地圖中標明牆邊道路。而且一旦撞了牆，就需要趕快沿着原路返回，可以在避免機器人走丟的同時減少步數。

由上，可以推斷出確定機器人是否在特定格子的試錯法：將機器人在不走到未知格子或已知傳送門的情況下走到牆邊的道路上，然後繞着牆邊道路走一圈。這個過程中如果沒有撞牆，就可以確定機器人確實是在特定格子。

我們可以採用上面的方法，一開始標出圖中所有未知格子，然後從上到下，從左到右依次判斷每個未知格子是否是傳送門。可以先走到未知格子上方，然後向下、向左走。再用上面的方法判斷機器人是不是在未知格子的左側。如果不是，説明機器人不在應該在的位置，即未知格子是傳送門。

找出未知格子後就需要判斷 2k 個未知格子的配對關係，實際方法也很簡單：只需要暴力配對就可以了。由於 \(k \le 5\)，所以最多隻需要 \(9 + 7 + 5 + 3\) 次試錯法。作為對比，判斷圖中全部未知格子的情況最多需要 \(121 - 40\) 次試錯法。

由於目前下面這一份代碼只能通過 UOJ 的鏡像題：#247.【Rujia Liu's Present 7】Mysterious Space Station，而無法通過 UVa 原題。修改了 UOJ 上劉汝佳的標程後還是無法通過，並且暫時無法聯繫到劉汝佳。所以下面的代碼以 UOJ 為準。

不過劉汝佳的標程質量還是比下面這份代碼質量高很多的，可以在 UOJ 上查看到 通過了 UOJ 鏡像題的標程。同一份數據下，標程使用的移動次數非常少。

參考代碼 
  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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>

#define Wall 0
#define Unknown 1
#define Space 2
#define Gate 3
#define Path 4

const int N = 20;
const int dir[8][2] = {{0, 1},  {1, 0}, {0, -1}, {-1, 0},
                       {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
const char dirs[5] = "ESWN";
int n, m, k;
int a[N][N], id[N][N];

struct point {
  int x, y;

  point(int x = 0, int y = 0) : x(x), y(y) {}

  bool operator==(const point& tmp) const { return x == tmp.x && y == tmp.y; }

  bool operator!=(const point& tmp) const { return !(*this == tmp); }

  point side(int d) const { return point(x + dir[d][0], y + dir[d][1]); }

  int check(int d) { return a[x + dir[d][0]][y + dir[d][1]]; }

  int id() { return ::id[x][y]; }
} start;

std::vector<std::pair<point, int>> path;
std::pair<point, point> ans[N];
std::pair<point, bool> vis[N];

bool walk(int d) {
  printf("MoveRobot %c\n", dirs[d]);
  fflush(stdout);
  int ret;
  scanf("%d", &ret);
  return ret;
}

bool walk(int d, std::stack<int>& st) {
  if (walk(d)) {
    st.push(d);
    return true;
  }
  return false;
}

bool read() {
  if (scanf("%d%d%d", &n, &m, &k) != 3) return false;
  if (n == 0) return false;
  memset(a, 0, sizeof(a));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      char c;
      std::cin >> c;
      if (c == 'S') start = point(i, j);
      if (c == '*')
        a[i][j] = Wall;
      else
        a[i][j] = Unknown;
    }
  return true;
}

void answer() {
  for (int i = 0; i < k; i++)
    printf("Answer %d %d\n", ans[i].first.id(), ans[i].second.id());
  fflush(stdout);
}

// 單手扶牆法，因為靠牆的 Path 是極大閉合環，所以只需要在沿着 Path
// 走的過程中沒有碰到障礙就可以了
void wall_follower_init(point x, int last, int wallside, point s) {
  if (x == s && !path.empty()) return;
  if (x.check(wallside) == Path) {
    path.push_back(std::make_pair(x, wallside));
    wall_follower_init(x.side(wallside), wallside, last ^ 2, s);
  } else if (x.check(last) == Wall) {
    for (int i = 0; i < 4; i++)
      if (i != (last ^ 2) && x.check(i) != Wall) {
        path.push_back(std::make_pair(x, i));
        wall_follower_init(x.side(i), i, last, s);
        return;
      }
  } else {
    path.push_back(std::make_pair(x, last));
    wall_follower_init(x.side(last), last, wallside, s);
  }
}

void init() {
  int cnt = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      if (a[i][j] == Unknown) {
        id[i][j] = cnt++;
        for (int k = 0; k < 8; k++)
          if (point(i, j).check(k) == Wall) {
            a[i][j] = Path;
            break;
          }
      } else
        id[i][j] = 0;
    }
  path.clear();
  int wallside = 0, last = 0;
  for (int i = 0; i < 4; i++)
    if (start.check(i) == Wall) {
      wallside = i;
      break;
    }
  for (int i = 0; i < 4; i++)
    if (start.check(i) == Path && i != (wallside ^ 2)) {
      last = i;
      break;
    }
  wall_follower_init(start, last, wallside, start);
}

void undo(std::stack<int>& st) {
  while (!st.empty()) walk(st.top() ^ 2), st.pop();
}

bool wall_follower(point x) {
  std::stack<int> st;
  bool ok = true;
  int i = 0;
  while (i < path.size() && path[i].first != x) i++;
  for (int j = i; ok && j < path.size(); j++) {
    if (walk(path[j].second))
      st.push(path[j].second);
    else
      ok = false;
  }
  for (int j = 0; ok && j < i; j++) {
    if (walk(path[j].second))
      st.push(path[j].second);
    else
      ok = false;
  }
  if (ok == false) undo(st);
  return ok;
}

// 確定自己當前在
// x，使用「摸着石頭過河」的方法，只需要沿着可以避開障礙、未知格子和傳送門的方向走到
// Path 就行。 在找傳送門和配對傳送門時使用
void bfs(point s, point t, std::vector<int>& v) {
  static int map[N][N] = {};
  memset(map, -1, sizeof(map));
  std::queue<point> q;
  map[s.x][s.y] = 4;
  q.push(s);
  while (!q.empty()) {
    point x = q.front();
    q.pop();
    if (x == t) break;
    for (int i = 0; i < 4; i++) {
      point y = x.side(i);
      if ((x.check(i) == Path || x.check(i) == Space) && map[y.x][y.y] == -1) {
        map[y.x][y.y] = i;
        q.push(y);
      }
    }
  }
  for (point x = t; x != s; x = x.side(map[x.x][x.y] ^ 2)) {
    v.push_back(map[x.x][x.y]);
  }
  std::reverse(v.begin(), v.end());
}

bool move(point s, point t, std::stack<int>& st) {  // 在靠近傳送門時使用
  static std::vector<int> v;
  v.clear();
  bfs(s, t, v);
  for (int i : v)
    if (walk(i, st) == false) return false;
  return true;
}

// 儘可能快地向牆邊移動
bool make_sure(point x, int last) {
  if (a[x.x][x.y] == Path) return wall_follower(x);
  for (int i = 0; i < 4; i++)
    if ((x.check(i) == Path || x.check(i) == Space) && i != (last ^ 2)) {
      if (!walk(i)) return false;
      bool ret = make_sure(x.side(i), i);
      walk(i ^ 2);
      return ret;
    }
  return false;
}

void find_gate() {
  int cnt = 0;
  std::stack<int> st;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (cnt == k * 2 && a[i][j] == Unknown)
        a[i][j] = Space;
      else if (a[i][j] == Unknown) {
        bool ok = true;
        if (!move(start, point(i - 1, j), st))
          ok = false;
        else if (!walk(1, st))
          ok = false;
        else if (!walk(2, st))
          ok = false;
        else if (!make_sure(point(i, j - 1), -1))
          ok = false;
        if (ok == false) {
          vis[cnt++] = std::make_pair(point(i, j), false);
          a[i][j] = Gate;
          for (int k = 0; k < 8; k++) {
            point y = point(i, j).side(k);
            if (point(i, j).check(k) == Unknown) a[y.x][y.y] = Space;
          }
        } else
          a[i][j] = Space;
        undo(st);
      }
}

void make_gate_pair() {
  int cnt = 0;
  std::stack<int> st;
  for (int i = 0; i < k * 2; i++)
    if (vis[i].second == false)
      for (int j = 0; vis[i].second == false && j < k * 2; j++)
        if (j != i && vis[j].second == false) {
          bool ok = true;
          if (!move(start, vis[i].first.side(2), st))
            ok = false;
          else if (!walk(0, st))
            ok = false;
          else if (!make_sure(vis[j].first.side(0), -1))
            ok = false;
          if (ok == true) {
            ans[cnt++] = std::make_pair(vis[i].first, vis[j].first);
            vis[i].second = vis[j].second = true;
          }
          undo(st);
        }
}

int main() {
  while (read()) {
    init();
    find_gate();
    make_gate_pair();
    answer();
  }
  return 0;
}

習題

參考資料與拓展閲讀

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：countercurrent-time, StudyingFather
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用