AtCoder AT_abc405_d ABC405D - Escape Route

前言

BFS 算法在 AtCoder 比赛中照旧会考的，因为不常训练导致没想到，不仅错误 TLE 了很多，还影响了心态，3 发罚时后才 AC。
思路

起首，我们把全部位置和出口的隔断算出来（用 BFS），记为                                              d                                       x                               ,                               y                                                 d_{x,y}                  dx,y​，顺便求出离它近来的出口坐标，记为                                    (                                   X                                       x                               ,                               y                                            ,                                   Y                                       x                               ,                               y                                            )                              (X_{x,y},Y_{x,y})                  (Xx,y​,Yx,y​)。我们发现这个必要在队列里记下这个点的近来出口位置以及具体坐标。
然后我们像荡漾一样扩散着用 BFS 去求方向。找每个位置的上一步，然后判断是否是一条路上的（即近来出口相同且隔断大于这个点的隔断），假如是，那么修改方向并压入队列，否则忽略。
似乎很成功地做完了，那么有哪些易错点呢？

• 更新方向的时候肯定要注意隔断是否大于当前点的隔断。注意：必须是严格大于，等于也不可以，因为加上这一步之后就不是最优。
  
• 记得把安全疏散出口的近来出口位置设为它自己。
  
• 肯定要用 BFS，而不是 DFS，两个函数都得用 BFS。
  

代码

AC 提交记录：Submission #65683293。
TLE 提交记录：第一发、第二发、第三发。

1. #include <cstdio>
2. #include <iostream>
3. #include <algorithm>
4. #include <cstring>
5. #include <queue>
6. using namespace std;
8. int h, w, d[1010][1010];
9. char a[1010][1010];
10. pair<int, int> p[1010][1010];
11. int dx[] = {-1, 1, 0, 0};
12. int dy[] = {0, 0, -1, 1};
13. char cc[] = {'v', '^', '>', '<'};
15. void work()
16. {
17.         queue<pair<pair<int, int>, pair<int, int> > > q;
18.         for (int x = 1; x <= h; x++)
19.                 for (int y = 1; y <= w; y++)
20.                         if (a[x][y] == 'E')
21.                         {
22.                                 p[x][y] = make_pair(x, y);
23.                                 q.push(make_pair(make_pair(x, y), make_pair(x, y)));
24.                                 d[x][y] = 0;
25.                         }
26.         while (q.size())
27.         {
28.                 int fx = q.front().first.first;
29.                 int fy = q.front().first.second;
30.                 int xx = q.front().second.first;
31.                 int yy = q.front().second.second;
32.                 q.pop();
33.                 for (int i = 0; i < 4; i++)
34.                 {
35.                         int nx = fx + dx[i];
36.                         int ny = fy + dy[i];
37.                         if (nx < 1 || nx > h)
38.                                 continue;
39.                         if (ny < 1 || ny > w)
40.                                 continue;
41.                         if (a[nx][ny] != '.')
42.                                 continue;
43.                         if (d[nx][ny] > d[fx][fy] + 1)
44.                         {
45.                                 d[nx][ny] = d[fx][fy] + 1;
46.                                 p[nx][ny] = make_pair(xx, yy);
47.                                 q.push(make_pair(make_pair(nx, ny), make_pair(xx, yy)));
48.                         }
49.                 }
50.         }
51. }
53. void calc()
54. {
55.         queue<pair<int, int> > q;
56.         for (int x = 1; x <= h; x++)
57.                 for (int y = 1; y <= w; y++)
58.                         if (a[x][y] == 'E')
59.                                 q.push(make_pair(x, y));
60.         while (q.size())
61.         {
62.                 int fx = q.front().first;
63.                 int fy = q.front().second;
64.                 q.pop();
65.                 for (int i = 0; i < 4; i++)
66.                 {
67.                         int nx = fx + dx[i];
68.                         int ny = fy + dy[i];
69.                         if (nx < 1 || nx > h)
70.                                 continue;
71.                         if (ny < 1 || ny > w)
72.                                 continue;
73.                         if (a[nx][ny] != '.')
74.                                 continue;
75.                         if (p[nx][ny] != p[fx][fy])
76.                                 continue;
77.                         if (d[nx][ny] <= d[fx][fy])
78.                                 continue;
79.                         a[nx][ny] = cc[i];
80.                         q.push(make_pair(nx, ny));
81.                 }
82.         }
83. }
85. int main()
86. {
87.         cin >> h >> w;
88.         for (int i = 1; i <= h; i++)
89.                 for (int j = 1; j <= w; j++)
90.                         cin >> a[i][j];
91.         memset(d, 0x3f, sizeof(d));
92.         work();
93.         calc();
94.         for (int i = 1; i <= h; i++)
95.         {
96.                 for (int j = 1; j <= w; j++)
97.                         cout << a[i][j];
98.                 cout << endl;
99.         }
100.         return 0;
101. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。