题目描述

平方取模迷宫

在一个 m 行 n 列的迷宫中，每个格子都有一个整数。你从起点(qx,qy) 出发，初始能量值为起点的格子值。每次你可以向上、下、左、右四个方向移动一格，但不能走出迷宫，也不能重复经过同一个格子。

每当你移动到一个新格子时，你的能量值会按照以下规则更新：

新能量值=(当前能量值+新格子的值)^2modq

你的目标是到达终点 (zx,zy)，并且到达时能量值恰好等于 w。求最少需要移动多少步。

如果无法在 16 步以内（包含 16 步） 到达终点并满足条件，则输出 -1。

输入格式

第一行包含两个整数 m 和 n,表示迷宫的行数和列数。（1≤n≤m≤900） 第二行包含四个整数 qx,qy,zx,zy，分别表示起点的行、列和终点的行、列。坐标从 1 开始。

第三行包含两个整数 q 和 w，分别表示取模的模数和目标能量值。 接下来 m 行，每行 n 个整数，表示迷宫中每个格子的值。第 i 行第 j 列的值对应格子 (i,j)。

输出格式

输出一个整数，表示最少步数。如果无法在 16 步内到达终点并满足条件，输出 -1。

3 3
1 1 3 3
100 4
1 2 3
4 5 6
7 8 9

-1

3 3
1 1 3 3
1000 604
1 2 3
4 5 6
7 8 9

6

数据范围与约定

数据范围 1≤n≤m≤900

1≤qx,zx≤m，

1≤qy,zy≤n

1≤q≤10

0≤w<q

起点不参与能量计算，初始能量直接为起点的格子值。

每次移动后，能量值更新为 (当前能量 + 新格子值)^2 % q。

不能重复经过同一个格子。

如果 16 步内无法到达终点或到达时能量值不等于 w，输出 -1。