ACM中的AC题

[题目链接](https://www.nowcoder.com/practice/b56db882e9f94aed81b0a9d00da0ebff)

思路

两个玩家从同一起点出发，每步必须同时朝相反方向移动。当某人踩到传送门 @ 后离开，剩下的人可以自由移动。求两人都离开的最少步数。

关键观察：镜像约束压缩状态

如果两人都未离开，玩家 1 走 $(dx, dy)$ ，玩家 2 必须走 $(-dx, -dy)$ 。设起点为 $(sr, sc)$ ，经过若干步后玩家 1 在 $(r_1, c_1)$ ，玩家 2 在 $(r_2, c_2)$ ，则始终满足：

$ $r_1 + r_2 = 2 \cdot sr, \quad c_1 + c_2 = 2 \cdot sc$ $

因此只要知道玩家 1 的位置，就能推出玩家 2 的位置。双人阶段的状态空间只有 $O(n \times m)$ 而非 $O(n^2 \times m^2)$ 。

三阶段 BFS

将问题分成三个阶段，用统一的 BFS 搜索：

阶段 0：两人都在场。状态 = 玩家 1 的坐标 $(r, c)$ （玩家 2 的坐标由镜像关系自动确定）。每次枚举 4 个方向，同时计算两人的新位置，检查越界和陷阱。
阶段 1：玩家 1 已通过传送门离开，玩家 2 单独自由移动。状态 = 玩家 2 的坐标。
阶段 2：玩家 2 已通过传送门离开，玩家 1 单独自由移动。状态 = 玩家 1 的坐标。

转移细节

阶段 0 中，对于每个方向 $d$ ：

计算玩家 1 新位置 $(nr_1, nc_1)$ 和玩家 2 新位置 $(nr_2, nc_2) = (2 \cdot sr - r - dx_d, 2 \cdot sc - c - dy_d)$ ；
若任一越界或踩陷阱，跳过；
若两人都踩到传送门，直接输出 steps + 1；
若只有玩家 1 踩传送门，转入阶段 1，初始位置为 $(nr_2, nc_2)$ ；
若只有玩家 2 踩传送门，转入阶段 2，初始位置为 $(nr_1, nc_1)$ ；
否则停留在阶段 0，状态更新为 $(nr_1, nc_1)$ 。

阶段 1 / 2 就是普通的单人 BFS，遇到传送门即结束。

由于使用统一的 BFS 队列，阶段之间的转换自然衔接，且保证最短路性质。

样例演示

以样例 1 为例：3x3 地图，起点 $(2,2)$ （1-indexed），四角都是传送门。

第 1 步选上，玩家 1 到 $(1,2)$ ，玩家 2 到 $(3,2)$ ；第 2 步选左，玩家 1 到 $(1,1)$ （传送门），玩家 2 到 $(3,3)$ （传送门），两人同时离开，答案为 2。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, sr, sc;
    cin >> n >> m >> sr >> sc;
    sr--; sc--;

    vector<string> grid(n);
    for(int i = 0; i < n; i++) cin >> grid[i];

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    // dist[phase][r][c], phase: 0=both active, 1=p1 escaped, 2=p2 escaped
    vector<vector<vector<int>>> dist(3, vector<vector<int>>(n, vector<int>(m, -1)));

    struct State { int phase, r, c; };
    queue<State> q;
    dist[0][sr][sc] = 0;
    q.push({0, sr, sc});

    while(!q.empty()){
        auto [phase, r, c] = q.front(); q.pop();
        int steps = dist[phase][r][c];

        if(phase == 0){
            for(int d = 0; d < 4; d++){
                int nr1 = r + dx[d], nc1 = c + dy[d];
                int nr2 = 2*sr - r - dx[d], nc2 = 2*sc - c - dy[d];
                if(nr1 < 0 || nr1 >= n || nc1 < 0 || nc1 >= m) continue;
                if(nr2 < 0 || nr2 >= n || nc2 < 0 || nc2 >= m) continue;
                if(grid[nr1][nc1] == '#' || grid[nr2][nc2] == '#') continue;

                bool p1p = grid[nr1][nc1] == '@';
                bool p2p = grid[nr2][nc2] == '@';

                if(p1p && p2p){
                    cout << steps + 1 << endl;
                    return 0;
                } else if(p1p){
                    if(dist[1][nr2][nc2] == -1){
                        dist[1][nr2][nc2] = steps + 1;
                        q.push({1, nr2, nc2});
                    }
                } else if(p2p){
                    if(dist[2][nr1][nc1] == -1){
                        dist[2][nr1][nc1] = steps + 1;
                        q.push({2, nr1, nc1});
                    }
                } else {
                    if(dist[0][nr1][nc1] == -1){
                        dist[0][nr1][nc1] = steps + 1;
                        q.push({0, nr1, nc1});
                    }
                }
            }
        } else {
            for(int d = 0; d < 4; d++){
                int nr = r + dx[d], nc = c + dy[d];
                if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if(grid[nr][nc] == '#') continue;
                if(grid[nr][nc] == '@'){
                    cout << steps + 1 << endl;
                    return 0;
                }
                if(dist[phase][nr][nc] == -1){
                    dist[phase][nr][nc] = steps + 1;
                    q.push({phase, nr, nc});
                }
            }
        }
    }

    cout << -1 << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int sr = Integer.parseInt(st.nextToken()) - 1;
        int sc = Integer.parseInt(st.nextToken()) - 1;

        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine().toCharArray();
        }

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        int[][][] dist = new int[3][n][m];
        for (int[][] a : dist) for (int[] b : a) Arrays.fill(b, -1);

        Queue<int[]> queue = new LinkedList<>();
        dist[0][sr][sc] = 0;
        queue.add(new int[]{0, sr, sc});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int phase = cur[0], r = cur[1], c = cur[2];
            int steps = dist[phase][r][c];

            if (phase == 0) {
                for (int d = 0; d < 4; d++) {
                    int nr1 = r + dx[d], nc1 = c + dy[d];
                    int nr2 = 2 * sr - r - dx[d], nc2 = 2 * sc - c - dy[d];
                    if (nr1 < 0 || nr1 >= n || nc1 < 0 || nc1 >= m) continue;
                    if (nr2 < 0 || nr2 >= n || nc2 < 0 || nc2 >= m) continue;
                    if (grid[nr1][nc1] == '#' || grid[nr2][nc2] == '#') continue;

                    boolean p1p = grid[nr1][nc1] == '@';
                    boolean p2p = grid[nr2][nc2] == '@';

                    if (p1p && p2p) {
                        System.out.println(steps + 1);
                        return;
                    } else if (p1p) {
                        if (dist[1][nr2][nc2] == -1) {
                            dist[1][nr2][nc2] = steps + 1;
                            queue.add(new int[]{1, nr2, nc2});
                        }
                    } else if (p2p) {
                        if (dist[2][nr1][nc1] == -1) {
                            dist[2][nr1][nc1] = steps + 1;
                            queue.add(new int[]{2, nr1, nc1});
                        }
                    } else {
                        if (dist[0][nr1][nc1] == -1) {
                            dist[0][nr1][nc1] = steps + 1;
                            queue.add(new int[]{0, nr1, nc1});
                        }
                    }
                }
            } else {
                for (int d = 0; d < 4; d++) {
                    int nr = r + dx[d], nc = c + dy[d];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                    if (grid[nr][nc] == '#') continue;
                    if (grid[nr][nc] == '@') {
                        System.out.println(steps + 1);
                        return;
                    }
                    if (dist[phase][nr][nc] == -1) {
                        dist[phase][nr][nc] = steps + 1;
                        queue.add(new int[]{phase, nr, nc});
                    }
                }
            }
        }

        System.out.println(-1);
    }
}

复杂度分析

时间复杂度： $O(n \times m)$ 。三个阶段各自的状态空间都是 $O(n \times m)$ ，每个状态最多入队一次，每次扩展 4 个方向。
空间复杂度： $O(n \times m)$ 。存储三个阶段的距离数组。