HJ162 ACM中的AC题

• 题目
• 题解(8)
• 讨论(3)
• 排行

中等 通过率：19.65% 时间限制：1秒 空间限制：256M

知识点广度优先搜索(BFS)

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

众所周知，出题人没玩过《双人成行》，于是给出了如下经典二人协作版迷宫问题。孤岛被划分为 n×mn×m 个方格，按行从上到下、列从左到右编号为 (1,1)(1,1) 至 (n,m)(n,m)。地图上的地形分为三种：
∙ ∙平地（`.`）——可以自由经过；
∙ ∙陷阱（`#`）——踩上去立即死亡；
∙ ∙传送门（`@`）——一旦进入便会立刻离开孤岛。

你与来自平行时空的另一个"你"最初同时位于坐标 (x,y)(x,y) 的同一块平地。两人每次必须同时行动，且朝相反方向各移动一步，即：
∙ ∙如果你选择向上，则另一个你必须向下；
∙ ∙如果你选择向左，则另一个你必须向右，依此类推。

在任何时刻，若有人走出边界或踏入陷阱，游戏立即失败；若有人到达传送门，则他会立刻离开并不再返回，之后剩下的那个人可以单独自由移动（不再受"相反方向"限制）。

请判断是否存在一条合法的移动序列，使得两个人都能成功离开孤岛；若存在，请输出最短所需步数，否则输出 −1−1。

输入描述：

输入包含 n+1n+1 行：
∙ ∙第一行输入四个整数 n,m,x,y(1≦n,m≦2×103; 1≦x≦n; 1≦y≦m)n,m,x,y(1≦n,m≦2×103; 1≦x≦n; 1≦y≦m)；
∙ ∙接下来 nn 行，第 ii 行输入一个长度为 mm 的字符串 sisi​，仅由 `.`、`#`、`@` 组成，描述第 ii 行的地形。
保证起点 (x,y)(x,y) 处为平地。

输出描述：

若存在可行方案，输出最短移动步数；否则输出 −1−1。

示例1

输入：

3 3 2 2 @.@ #.. @.@

复制输出：

2

复制说明：

你可以先往上后往左到达(1,1)传送门

另外一个时空的你会先下后右到达(3,3)传送门

示例2

输入：

1 3 1 2 ..@

复制输出：

3

复制

示例3

输入：

3 1 2 1 # . @

复制输出：

-1

复制说明：

显然，谁都不想走到陷阱那 ...

#include <iostream> #include <vector> #include <string> #include <queue> #include <tuple> using namespace std; const int INF = 1e9; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m, r_start, c_start; cin >> n >> m >> r_start >> c_start; --r_start; --c_start; // 0-indexed vector<string> grid(n); for (int i = 0; i < n; ++i) { cin >> grid[i]; } // Step 1: Multi-source BFS for solo phase vector<vector<int>> dist_solo(n, vector<int>(m, -1)); queue<pair<int, int>> q_solo; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j] == '@') { dist_solo[i][j] = 0; q_solo.push({i, j}); } } } int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; while (!q_solo.empty()) { auto [r, c] = q_solo.front(); q_solo.pop(); for (int i = 0; i < 4; ++i) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#' && dist_solo[nr][nc] == -1) { dist_solo[nr][nc] = dist_solo[r][c] + 1; q_solo.push({nr, nc}); } } } // Step 2: BFS for paired phase vector<vector<int>> dist_pair(n, vector<int>(m, -1)); queue<pair<int, int>> q_pair; dist_pair[r_start][c_start] = 0; q_pair.push({r_start, c_start}); while (!q_pair.empty()) { auto [r1, c1] = q_pair.front(); q_pair.pop(); int r2 = 2 * r_start - r1; int c2 = 2 * c_start - c1; for (int i = 0; i < 4; ++i) { int nr1 = r1 + dr[i]; int nc1 = c1 + dc[i]; int nr2 = r2 - dr[i]; int nc2 = c2 - dc[i]; if (nr1 >= 0 && nr1 < n && nc1 >= 0 && nc1 < m && grid[nr1][nc1] != '#' && nr2 >= 0 && nr2 < n && nc2 >= 0 && nc2 < m && grid[nr2][nc2] != '#' && dist_pair[nr1][nc1] == -1) { dist_pair[nr1][nc1] = dist_pair[r1][c1] + 1; q_pair.push({nr1, nc1}); } } } // Step 3: Combine results long long min_total_time = -1; for (int r1 = 0; r1 < n; ++r1) { for (int c1 = 0; c1 < m; ++c1) { if (dist_pair[r1][c1] != -1) { long long t_pair = dist_pair[r1][c1]; int r2 = 2 * r_start - r1; int c2 = 2 * c_start - c1; if (grid[r1][c1] == '@' && dist_solo[r2][c2] != -1) { long long current_time = t_pair + dist_solo[r2][c2]; if (min_total_time == -1 || current_time < min_total_time) { min_total_time = current_time; } } if (grid[r2][c2] == '@' && dist_solo[r1][c1] != -1) { long long current_time = t_pair + dist_solo[r1][c1]; if (min_total_time == -1 || current_time < min_total_time) { min_total_time = current_time; } } } } } cout << min_total_time << endl; return 0; }