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。输入描述输入包含 n1n1 行∙ ∙第一行输入四个整数 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 vectorstring grid(n); for (int i 0; i n; i) { cin grid[i]; } // Step 1: Multi-source BFS for solo phase vectorvectorint dist_solo(n, vectorint(m, -1)); queuepairint, 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 vectorvectorint dist_pair(n, vectorint(m, -1)); queuepairint, 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; }