HJ161 走一个大整数迷宫

题目题解(10)讨论(4)排行中等 通过率40.12% 时间限制1秒 空间限制256M知识点广度优先搜索(BFS)校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定一个 n×mn×m 的矩阵迷宫其中第 ii 行第 jj 列的格子权值为ci,jai,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; vectorvectorint a(n, vectorint(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin a[i][j]; } } // b矩阵在计算余数时是不需要的但仍需读入以消耗输入 vectorvectorint b(n, vectorint(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; vectorvectorvectorint dist(n, vectorvectorint(m, vectorint(mod, -1))); queueState 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; }