首页 > 试题广场 >

走一个大整数迷宫

[编程题]走一个大整数迷宫
  • 热度指数：82 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个 n \times m 的矩阵迷宫，其中第 i 行第 j 列的格子权值为

c_{i,j}=a_{i,j}\times p^{2^{b_{i,j}}}。

\hspace{15pt}LH 起始位于 (1,1)，出口位于 (n,m)。迷宫配有一个计数器，初始值为 c_{1,1}。在任意时刻，若计数器的值满足 \text{counter} \equiv 0 \pmod{(p-1)}，且 LH 身处出口 (n,m)，大门即刻打开，LH 得以逃离。

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

\hspace{15pt}请计算 LH 最快需要多少秒才能逃离；若无论如何都无法逃离，则输出 -1。

输入描述:
\hspace{15pt}输入共三部分：
\hspace{23pt}\bullet\,第一行输入三个整数 n,m,p\left(1\leqq n,m\leqq 10;\ 2\leqq p\leqq 10^{4}\right)；
\hspace{23pt}\bullet\,接下来 n 行，每行 m 个整数，构成矩阵 a_{i,j}；
\hspace{23pt}\bullet\,再接下来 n 行，每行 m 个整数，构成矩阵 b_{i,j}，范围均为 0\leqq a_{i,j},b_{i,j}\leqq 10^{6}。


输出描述:
\hspace{15pt}输出一个整数，代表最短逃离时间；若无法逃离，输出 -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=\begin{bmatrix}<br /> 100 &20  &30 \\<br />  0& 10 & 400\\<br />  0& 0 &0<br />\end{bmatrix}。

第一秒，从 (1,1) 走到 (1,2)，计数器的值为 120。

第二秒，从 (1,2) 走到 (1,3)，计数器的值为 150。

第三秒，从 (1,3) 走到 (1,2)，计数器的值为 170。

第四秒，从 (1,2) 走到 (2,2)，计数器的值为 180。

第五秒，从 (2,2) 走到 (3,2)，计数器的值为 180。

第六秒，从 (3,2) 走到 (3,3)，计数器的值为 180，是 9 的倍数，逃出迷宫。

img
算法知识视频讲解
添加回答
牛客348448733号头像 牛客348448733号
p≡1(modp−1)，所以ci,j=ai,j，b不需要处理
发表于 今天 04:29:43 回复(0)
提交观点

问题信息

广度优先搜索(BFS)
难度：
1条回答 21浏览

热门推荐

相关试题

走一个大整数迷宫

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号