题面:https://www.luogu.com.cn/problem/P1825
这题显然是BFS,于是光速写完,交了一发WA了。
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
| #include <cctype> #include <cstdio> #include <cstdlib> #include <iostream> #include <ostream> #include <queue> #include <unordered_map> #include <utility> #include <vector> using namespace std; const int MAX_SIZE = 304; int n, m; char g[MAX_SIZE][MAX_SIZE]; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int s_row, s_col, e_row, e_col; unordered_map<char, vector<pair<int, int>>> trans; bool vis[MAX_SIZE][MAX_SIZE]; struct State { int row; int col; int step; }; int main(int argc, const char *argv[]) { cin >> n >> m; for (int i = 1; i <= n; i++) { scanf("%s", g[i] + 1); for (int j = 1; j <= m; j++) { if (g[i][j] == '@') { s_row = i; s_col = j; } else if (g[i][j] == '=') { e_row = i; e_col = j; } else if (isalpha(g[i][j])) { trans[g[i][j]].emplace_back(make_pair(i, j)); } } } queue<State> q; q.emplace(State{s_row, s_col, 0}); vis[s_row][s_col] = true; while (!q.empty()) { State old = q.front(); q.pop(); for (int d = 0; d < 4; ++d) { int n_row = old.row + dir[d][0]; int n_col = old.col + dir[d][1]; if (n_row < 1 || n_row > n || n_col < 1 || n_col > m) { continue; } else if (vis[n_row][n_col]) { continue; } else if (g[n_row][n_col] == '#') { continue; } vis[n_row][n_col] = true; if (isalpha(g[n_row][n_col])) { auto poses = trans[g[n_row][n_col]]; if (poses[0].first == n_row && poses[0].second == n_col) { n_row = poses[1].first; n_col = poses[1].second; } else { n_row = poses[0].first; n_col = poses[0].second; } vis[n_row][n_col] = true; } if (n_row == e_row && n_col == e_col) { cout << old.step + 1 << endl; exit(0); } q.emplace(State{n_row, n_col, old.step + 1}); } } return 0; }
|
看了题解后大彻大悟:
上面的代码标记了传送点的vis
,这实际上是多此一举。比如下面这个例子,传送点A是作为中转点的,实际上走了两次。
1 2 3 4 5
| # # # # # # = # # # . . . . . . # # # # # A # # # # # # @ . . # A . . # # # # # # # # # #
|