题解 | #走一个大整数迷宫#

题目链接

走一个大整数迷宫

题目描述

给定一个 $n \times m$ 的矩阵迷宫。矩阵中第 $i$ 行 $j$ 列的格子的权值为 $c_{i,j} = a_{i,j} \cdot p^{2^{b_{i,j}}}$ 。

LH 从起点 $(1,1)$ 出发，目标是到达出口 $(n,m)$ 。迷宫配有一个计数器，其初始值为起点 $(1,1)$ 的权值 $c_{1,1}$ 。

LH 每秒必须从当前格子向上下左右四个相邻方向之一移动一格（不得停留或走出迷宫）。假设 LH 从 $(i,j)$ 移动到 $(i',j')$ ，计数器会累加 $c_{i',j'}$ 。

只有当 LH 身处出口 $(n,m)$ ，且计数器的总值 $counter$ 恰好满足 $counter \equiv 0 \pmod{p-1}$ 时，大门才会打开。

请计算 LH 逃离迷宫所需的最短时间（秒）。如果无论如何都无法逃离，则输出 $-1$ 。

解题思路

本题要求解在满足特定模数条件下，从起点到终点的最短路径。这是一个典型的广度优先搜索 (BFS) 问题，但需要对状态进行扩展。

问题的核心在于，能否到达终点不仅取决于位置，还取决于累积的权值和。由于退出条件只关心总权值对 $p-1$ 的余数，我们可以将搜索的状态定义为一个三元组 $(x, y, rem)$ ，其中：

$(x, y)$ 是 LH 当前所在的坐标。
$rem$ 是当前计数器总值对 $p-1$ 取模的余数。

由于我们寻求的是最短时间，且每次移动耗时固定为 1 秒，广度优先搜索 (BFS) 是解决此类问题的理想算法。BFS 能够保证我们第一次到达某个状态时，所用的时间（步数）是最短的。

状态转移的关键：权值简化

状态转移时，需要计算新位置的权值并更新余数。权值 $c_{i,j} = a_{i,j} \cdot p^{2^{b_{i,j}}}$ 的计算看起来非常复杂，但由于我们只关心它对 $p-1$ 的模，可以利用模运算的性质进行简化。

根据模运算的基本性质， $p \equiv 1 \pmod{p-1}$ 。对于任意大于等于 1 的整数 $k$ ，都有 $p^k \equiv 1^k \equiv 1 \pmod{p-1}$ 。

在题目中，权值公式的指数部分为 $2^{b_{i,j}}$ 。由于输入保证 $b_{i,j} \ge 0$ ，所以 $2^{b_{i,j}} \ge 2^0 = 1$ 。因此，指数部分总是大于等于 1。这意味着 $p^{2^{b_{i,j}}} \equiv 1 \pmod{p-1}$ 。

于是，每个格子的权值对 $p-1$ 取模后可以惊人地简化： $c_{i,j} \pmod{p-1} = (a_{i,j} \cdot p^{2^{b_{i,j}}}) \pmod{p-1}$ $c_{i,j} \pmod{p-1} = (a_{i,j} \pmod{p-1} \cdot p^{2^{b_{i,j}}} \pmod{p-1}) \pmod{p-1}$ $c_{i,j} \pmod{p-1} = (a_{i,j} \pmod{p-1} \cdot 1) \pmod{p-1}$ $c_{i,j} \pmod{p-1} = a_{i,j} \pmod{p-1}$

因此，在计算累计余数时，我们只需要考虑 $a_{i,j}$ 的值，而 $b_{i,j}$ 和 $p$ 本身（除了作为模数 $p-1$ 外）变得无关紧要。

算法流程

初始化：
- 创建一个三维数组 $dist[n][m][p-1]$ ，记录到达状态 $(x, y, rem)$ 的最短时间，所有元素初始化为 $-1$ 。
- 创建一个队列用于 BFS。
- 设 $mod = p-1$ 。
- 初始状态：时间 $t=0$ ，位置为 $(0,0)$ （采用 0-based 索引）。计数器值为 $c_{0,0}$ ，其初始余数 $rem_{init} = a_{0,0} \pmod{mod}$ 。
- 更新初始状态的距离： $dist[0][0][rem_{init}] = 0$ ，并将初始状态 $(0, 0, rem_{init})$ 入队。
BFS 搜索：
- 当队列不为空时，出队一个状态 $(curr_x, curr_y, curr_{rem})$ 。
- 获取到达该状态的时间 $t = dist[curr_x][curr_y][curr_{rem}]$ 。
- 对于当前位置的四个相邻格子 $(next_x, next_y)$ ：
  - 计算新的余数： $next_{rem} = (curr_{rem} + a_{next_x, next_y}) \pmod{mod}$ 。
  - 如果状态 $(next_x, next_y, next_{rem})$ 尚未被访问过（即 $dist[next_x][next_y][next_{rem}] == -1$ ）：
    - 更新该状态的最短时间： $dist[next_x][next_y][next_{rem}] = t + 1$ 。
    - 将新状态 $(next_x, next_y, next_{rem})$ 入队。
获取结果：
- BFS 结束后，我们需要找到达终点 $(n-1, m-1)$ 且满足余数条件的最短时间。
- 目标余数是 $0$ 。
- 因此，最终答案就是 $dist[n-1][m-1][0]$ 。若该值仍为 $-1$ ，则表示无法逃离。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct State {
    int x, y, rem;
};

int main() {
    int n, m, p;
    cin >> n >> m >> p;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    
    // b矩阵在计算余数时是不需要的，但仍需读入以消耗输入
    vector<vector<int>> b(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> b[i][j];
        }
    }

    if (p == 1) { // p-1 = 0, 无法取模
        cout << -1 << endl;
        return 0;
    }
    int mod = p - 1;

    vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(mod, -1)));
    queue<State> q;

    int start_rem = a[0][0] % mod;
    dist[0][0][start_rem] = 0;
    q.push({0, 0, start_rem});

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

    while (!q.empty()) {
        State curr = q.front();
        q.pop();

        int t = dist[curr.x][curr.y][curr.rem];

        for (int i = 0; i < 4; ++i) {
            int nx = curr.x + dx[i];
            int ny = curr.y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                int next_rem = (curr.rem + a[nx][ny]) % mod;
                
                if (dist[nx][ny][next_rem] == -1) {
                    dist[nx][ny][next_rem] = t + 1;
                    q.push({nx, ny, next_rem});
                }
            }
        }
    }

    cout << dist[n - 1][m - 1][0] << endl;

    return 0;
}

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

public class Main {
    static class State {
        int x, y, rem;

        State(int x, int y, int rem) {
            this.x = x;
            this.y = y;
            this.rem = rem;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();

        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        // b矩阵在计算余数时是不需要的，但仍需读入以消耗输入
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sc.nextInt();
            }
        }

        if (p == 1) { // p-1 = 0, 无法取模
            System.out.println(-1);
            return;
        }
        int mod = p - 1;

        int[][][] dist = new int[n][m][mod];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dist[i][j], -1);
            }
        }

        Queue<State> q = new LinkedList<>();

        int startRem = a[0][0] % mod;
        dist[0][0][startRem] = 0;
        q.offer(new State(0, 0, startRem));

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

        while (!q.isEmpty()) {
            State curr = q.poll();
            int t = dist[curr.x][curr.y][curr.rem];

            for (int i = 0; i < 4; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    int nextRem = (curr.rem + a[nx][ny]) % mod;
                    
                    if (dist[nx][ny][nextRem] == -1) {
                        dist[nx][ny][nextRem] = t + 1;
                        q.offer(new State(nx, ny, nextRem));
                    }
                }
            }
        }

        System.out.println(dist[n - 1][m - 1][0]);
    }
}

import sys
from collections import deque

def solve():
    try:
        n, m, p = map(int, input().split())
        
        a = [list(map(int, input().split())) for _ in range(n)]
        # b矩阵在计算余数时是不需要的，但仍需读入以消耗输入
        for _ in range(n):
            list(map(int, input().split()))

        if p == 1: # p-1 = 0, 无法取模
            print(-1)
            return

        mod = p - 1
        
        dist = [[[-1] * mod for _ in range(m)] for _ in range(n)]
        q = deque()

        start_rem = a[0][0] % mod
        dist[0][0][start_rem] = 0
        q.append((0, 0, start_rem))

        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]

        while q:
            x, y, rem = q.popleft()
            t = dist[x][y][rem]

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < n and 0 <= ny < m:
                    next_rem = (rem + a[nx][ny]) % mod
                    
                    if dist[nx][ny][next_rem] == -1:
                        dist[nx][ny][next_rem] = t + 1
                        q.append((nx, ny, next_rem))

        print(dist[n - 1][m - 1][0])

    except (IOError, ValueError):
        # 处理可能的输入结束或格式错误
        pass

solve()

算法及复杂度

算法：广度优先搜索 (BFS)
时间复杂度： $\mathcal{O}(n \cdot m \cdot p)$ 。状态的总数为 $n \cdot m \cdot (p-1)$ 。在 BFS 中，每个状态最多被访问一次，每次访问会尝试向四个方向扩展，因此总时间复杂度与状态总数成正比。
空间复杂度： $\mathcal{O}(n \cdot m \cdot p)$ 。空间开销主要来自于存储所有状态最短距离的 $dist$ 数组，以及 BFS 队列。
空间复杂度： $\mathcal{O}(N \cdot M \cdot K)$ 。空间开销主要来自于存储所有状态最短距离的 $dist$ 数组，以及 BFS 队列。