HJ161 走一个大整数迷宫

• 题目
• 题解(10)
• 讨论(4)
• 排行

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

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

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

描述

给定一个 n×mn×m 的矩阵迷宫，其中第 ii 行第 jj 列的格子权值为

ci,j=ai,j×p2bi,jci,j​=ai,j​×p2bi,j​。

LH 起始位于 (1,1)(1,1)，出口位于 (n,m)(n,m)。迷宫配有一个计数器，初始值为 c1,1c1,1​。在任意时刻，若计数器的值满足 counter≡0(mod(p−1))counter≡0(mod(p−1))，且 LH 身处出口 (n,m)(n,m)，大门即刻打开，LH 得以逃离。

每经过 11 秒，LH 必须向上、下、左、右四个方向中的某一方向移动一步（不得停留，也不得走出迷宫）。假设 LH 从 (i,j)(i,j) 移动到 (i′,j′)(i′,j′)，则计数器会累加 ci′,j′ci′,j′​。

请计算 LH 最快需要多少秒才能逃离；若无论如何都无法逃离，则输出 −1−1。

输入描述：

输入共三部分：
∙ ∙第一行输入三个整数 n,m,p(1≦n,m≦10; 2≦p≦104)n,m,p(1≦n,m≦10; 2≦p≦104)；
∙ ∙接下来 nn 行，每行 mm 个整数，构成矩阵 ai,jai,j​；
∙ ∙再接下来 nn 行，每行 mm 个整数，构成矩阵 bi,jbi,j​，范围均为 0≦ai,j,bi,j≦1060≦ai,j​,bi,j​≦106。

输出描述：

输出一个整数，代表最短逃离时间；若无法逃离，输出 −1−1。

示例1

输入：

3 3 10 1 2 3 0 1 4 0 0 0 1 0 0 0 0 1 0 1 0

复制输出：

6

复制说明：

C=[1002030010400000]C=⎣⎡​10000​20100​304000​⎦⎤​。 第一秒，从 (1,1)(1,1) 走到 (1,2)(1,2)，计数器的值为 120120。 第二秒，从 (1,2)(1,2) 走到 (1,3)(1,3)，计数器的值为 150150。 第三秒，从 (1,3)(1,3) 走到 (1,2)(1,2)，计数器的值为 170170。 第四秒，从 (1,2)(1,2) 走到 (2,2)(2,2)，计数器的值为 180180。 第五秒，从 (2,2)(2,2) 走到 (3,2)(3,2)，计数器的值为 180180。 第六秒，从 (3,2)(3,2) 走到 (3,3)(3,3)，计数器的值为 180180，是 99 的倍数，逃出迷宫。

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