题解 | #ACM中的AC题#

题目链接

双人成行

题目描述

在一个 $N \times M$ 的网格迷宫中，有平地(.)、陷阱(#)和传送门(@)。你和另一个你（记为玩家1和玩家2）同时从起点 $(R, C)$ 出发。

游戏分为两个阶段：

联动阶段：你们必须同时行动，且方向相反。例如，玩家1向上移动一格，玩家2必须向下移动一格。此阶段直到其中一人到达传送门时结束。
单人阶段：当一人通过传送门离开后，剩下的一人可以自由地向上下左右移动，直到也到达一个传送门。

在任何时候，任何人都不能移动到边界外或陷阱上。

请求出两人都成功离开迷宫的最短总步数。如果无法做到，输出 -1。

解题思路

这是一个复杂的最短路问题，我们可以将其分解为两个独立的子问题来解决：单人寻路和双人联动寻路。总的最短时间是这两个阶段用时之和的最小值。

步骤一：预计算单人阶段的最短时间

单人阶段的目标是从任意平地格子走到最近的传送门。这是一个典型的“多源最短路”问题，可以使用广度优先搜索（BFS）来高效解决。

我们定义一个距离数组 $dist\_solo[N][M]$ ，用于存储地图上每个点到最近传送门的最短距离。
初始化一个队列，并将所有传送门（@）的坐标加入队列，同时将它们在 $dist\_solo$ 数组中对应的距离设为 0。其他所有位置的距离初始化为 -1（表示不可达）。
运行 BFS。从队列中不断取出坐标，并扩展到其相邻的、未访问过的、且非陷阱的格子，更新这些格子的距离并将其入队。
BFS 结束后， $dist\_solo[r][c]$ 就保存了从格子 $(r, c)$ 出发，单人到达最近传送门所需的最短步数。

步骤二：计算联动阶段的最短时间

联动阶段也是一个最短路问题，同样可以用 BFS 解决。关键在于如何定义状态和状态转移。

状态定义：虽然有两个玩家，但他们的位置是相对起点中心对称的。如果我们知道玩家1的坐标 $(r_1, c_1)$ 和起点坐标 $(r_s, c_s)$ ，那么玩家2的坐标 $(r_2, c_2)$ 就可以通过公式 $r_2 = 2 \cdot r_s - r_1$ 和 $c_2 = 2 \cdot c_s - c_1$ 计算得出。因此，我们只需要用玩家1的坐标 $(r_1, c_1)$ 就可以唯一确定整个系统的状态。
我们定义另一个距离数组 $dist\_pair[N][M]$ ，用于存储联动阶段中，玩家1到达 $(r_1, c_1)$ 所需的最短步数。
状态转移：从起点 $(r_s, c_s)$ 开始 BFS。对于队列中取出的状态（玩家1的位置 $(r_1, c_1)$ ），我们尝试向四个方向 $(dr, dc)$ 移动。
- 玩家1的新位置为 $(r_1+dr, c_1+dc)$ 。
- 玩家2的新位置为 $(r_2-dr, c_2-dc)$ 。
- 我们必须检查这两个新位置是否都合法（即都在边界内且都不是陷阱）。
- 如果两个位置都合法，并且玩家1的新状态是首次到达，我们就更新 $dist\_pair$ 并将新状态入队。

步骤三：组合结果，寻找最优解

在完成上述两次 BFS 后，我们遍历所有可能的联动结束点，以找到总时间最短的方案。

初始化一个变量 $min\_total\_time$ 为无穷大。
遍历整个地图的每一个格子 $(r_1, c_1)$ 。
如果 $dist\_pair[r_1][c_1]$ 不是 -1（表示这个联动状态是可达的），设联动阶段用时为 $t = dist\_pair[r_1][c_1]$ 。
计算出此时玩家2的位置 $(r_2, c_2)$ 。
判断联动结束：
- 如果玩家1的位置 $(r_1, c_1)$ 是一个传送门，这意味着联动在此结束。玩家2需要从 $(r_2, c_2)$ 开始单人行动。如果 $dist\_solo[r_2][c_2]$ 可达，则我们找到了一个候选方案，总时间为 $t + dist\_solo[r_2][c_2]$ 。
- 同理，如果玩家2的位置 $(r_2, c_2)$ 是一个传送门，玩家1需要从 $(r_1, c_1)$ 开始单人行动。如果 $dist\_solo[r_1][c_1]$ 可达，总时间为 $t + dist\_solo[r_1][c_1]$ 。
用所有合法的候选方案更新 $min\_total\_time$ 。
最终，如果 $min\_total\_time$ 仍然是无穷大，说明无解，输出 -1；否则输出 $min\_total\_time$ 。

这种“预处理+搜索+组合”的思路将问题分解，使得逻辑清晰，易于实现。

代码

c++
java
python

#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;
}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

public class Main {
    static class Point {
        int r, c;
        Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int rStart = sc.nextInt() - 1; // 0-indexed
        int cStart = sc.nextInt() - 1;

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

        // Step 1: Multi-source BFS for solo phase
        int[][] distSolo = new int[n][m];
        for (int[] row : distSolo) Arrays.fill(row, -1);
        Queue<Point> qSolo = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '@') {
                    distSolo[i][j] = 0;
                    qSolo.offer(new Point(i, j));
                }
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!qSolo.isEmpty()) {
            Point p = qSolo.poll();
            for (int i = 0; i < 4; i++) {
                int nr = p.r + dr[i];
                int nc = p.c + dc[i];
                if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#' && distSolo[nr][nc] == -1) {
                    distSolo[nr][nc] = distSolo[p.r][p.c] + 1;
                    qSolo.offer(new Point(nr, nc));
                }
            }
        }

        // Step 2: BFS for paired phase
        int[][] distPair = new int[n][m];
        for (int[] row : distPair) Arrays.fill(row, -1);
        Queue<Point> qPair = new LinkedList<>();

        distPair[rStart][cStart] = 0;
        qPair.offer(new Point(rStart, cStart));

        while (!qPair.isEmpty()) {
            Point p1 = qPair.poll();
            int r2 = 2 * rStart - p1.r;
            int c2 = 2 * cStart - p1.c;

            for (int i = 0; i < 4; i++) {
                int nr1 = p1.r + dr[i];
                int nc1 = p1.c + 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] != '#' &&
                    distPair[nr1][nc1] == -1) {
                    distPair[nr1][nc1] = distPair[p1.r][p1.c] + 1;
                    qPair.offer(new Point(nr1, nc1));
                }
            }
        }

        // Step 3: Combine results
        long minTotalTime = -1;

        for (int r1 = 0; r1 < n; r1++) {
            for (int c1 = 0; c1 < m; c1++) {
                if (distPair[r1][c1] != -1) {
                    long tPair = distPair[r1][c1];
                    int r2 = 2 * rStart - r1;
                    int c2 = 2 * cStart - c1;

                    if (grid[r1][c1] == '@' && distSolo[r2][c2] != -1) {
                        long currentTime = tPair + distSolo[r2][c2];
                        if (minTotalTime == -1 || currentTime < minTotalTime) {
                            minTotalTime = currentTime;
                        }
                    }
                    if (grid[r2][c2] == '@' && distSolo[r1][c1] != -1) {
                        long currentTime = tPair + distSolo[r1][c1];
                        if (minTotalTime == -1 || currentTime < minTotalTime) {
                            minTotalTime = currentTime;
                        }
                    }
                }
            }
        }
        System.out.println(minTotalTime);
    }
}

import sys
from collections import deque

def solve():
    n, m, r_start, c_start = map(int, input().split())
    r_start -= 1
    c_start -= 1
    
    grid = [input() for _ in range(n)]

    # Step 1: Multi-source BFS for solo phase
    dist_solo = [[-1] * m for _ in range(n)]
    q_solo = deque()
    
    for r in range(n):
        for c in range(m):
            if grid[r][c] == '@':
                dist_solo[r][c] = 0
                q_solo.append((r, c))

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while q_solo:
        r, c = q_solo.popleft()
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != '#' and dist_solo[nr][nc] == -1:
                dist_solo[nr][nc] = dist_solo[r][c] + 1
                q_solo.append((nr, nc))

    # Step 2: BFS for paired phase
    dist_pair = [[-1] * m for _ in range(n)]
    q_pair = deque()

    dist_pair[r_start][c_start] = 0
    q_pair.append((r_start, c_start))
    
    while q_pair:
        r1, c1 = q_pair.popleft()
        r2 = 2 * r_start - r1
        c2 = 2 * c_start - c1

        for i in range(4):
            nr1, nc1 = r1 + dr[i], c1 + dc[i]
            nr2, nc2 = r2 - dr[i], c2 - dc[i]
            
            if 0 <= nr1 < n and 0 <= nc1 < m and grid[nr1][nc1] != '#' and \
               0 <= nr2 < n and 0 <= nc2 < m and grid[nr2][nc2] != '#' and \
               dist_pair[nr1][nc1] == -1:
                dist_pair[nr1][nc1] = dist_pair[r1][c1] + 1
                q_pair.append((nr1, nc1))

    # Step 3: Combine results
    min_total_time = float('inf')
    found = False

    for r1 in range(n):
        for c1 in range(m):
            if dist_pair[r1][c1] != -1:
                t_pair = dist_pair[r1][c1]
                r2 = 2 * r_start - r1
                c2 = 2 * c_start - c1
                
                if grid[r1][c1] == '@':
                    if dist_solo[r2][c2] != -1:
                        min_total_time = min(min_total_time, t_pair + dist_solo[r2][c2])
                        found = True

                if grid[r2][c2] == '@':
                    if dist_solo[r1][c1] != -1:
                        min_total_time = min(min_total_time, t_pair + dist_solo[r1][c1])
                        found = True
    
    if not found:
        print(-1)
    else:
        print(min_total_time)

solve()

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度： $\mathcal{O}(N \cdot M)$ 。
- 计算单人最短路程 $dist\_solo$ 的多源 BFS 复杂度为 $\mathcal{O}(N \cdot M)$ 。
- 计算双人联动最短步数 $dist\_pair$ 的 BFS 复杂度为 $\mathcal{O}(N \cdot M)$ 。
- 最后组合结果的遍历复杂度为 $\mathcal{O}(N \cdot M)$ 。
- 总体时间复杂度为 $\mathcal{O}(N \cdot M)$ 。
空间复杂度： $\mathcal{O}(N \cdot M)$ 。
- 主要空间开销来自于存储距离的两个二维数组 $dist\_solo$ 和 $dist\_pair$ ，以及 BFS 使用的队列。