U681125 [YCU Cup] 栗山未来的幻境突围
题目背景
“没有未来的未来，不是我想要的未来。”
异界士栗山未来握紧了手中的血之剑。为了拯救神原秋人，她独自闯入了一只极其强大的妖梦所构筑的幻境结界中。
这个幻境是一个庞大的迷宫，周围弥漫着致死的妖气。幻境的结构每时每刻都在重组，但秋人通过灵力共振，将幻境的核心种子传递给了未来。
“我不高兴。”未来推了推红色的眼镜，她必须用最快的速度穿过这片死亡迷宫，到达秋人所在的终点。
题目描述
幻境可以被抽象为一个 N × M 的二维网格。网格中的格子分为两种：
* 0：表示安全的空地，未来可以安全通行。
* 1：表示凝结的妖气墙壁，绝对无法通行。
栗山未来目前身处起点坐标 (sx, sy)，她需要前往秋人所在的终点坐标 (ex, ey)。她每次可以向上下左右四个方向移动一格，每移动一格消耗 1 个单位的时间。
**【幻境生成规则】**
为了还原这个复杂的结界，你必须使用题目提供的生成器类，实例化该类后，依次获取每一个格子的状态，自行在代码中完成地图的拼接。
生成器类内部维护了当前格子的坐标状态。每次调用获取下一个格子的方法时，它会严格按照**从第 1 行到第 N 行，每行从第 1 列到第 M 列**的顺序，返回对应格子的状态。
请在你的代码中原样加入以下幻境生成器类（请根据你使用的编程语言进行选择）：
**C++ 选手幻境生成器类：**
~~~cpp
class MazeGenerator {
private:
unsigned int seed;
int n, m, p, sx, sy, ex, ey;
int current_i, current_j;
unsigned int next_rand() {
seed = seed * 1103515245 + 12345;
return (seed / 65536) % 32768;
}
public:
MazeGenerator(int _n, int _m, int _p, int _sx, int _sy, int _ex, int _ey, unsigned int _seed) {
n = _n; m = _m; p = _p;
sx = _sx; sy = _sy; ex = _ex; ey = _ey;
seed = _seed;
current_i = 1;
current_j = 1;
}
int next_cell() {
if (current_i > n) return -1;
int is_wall = 0;
if (current_i == sx && current_j == sy) {
is_wall = 0;
} else if (current_i == ex && current_j == ey) {
is_wall = 0;
} else {
is_wall = (next_rand() % 100 < p) ? 1 : 0;
}
current_j++;
if (current_j > m) {
current_j = 1;
current_i++;
}
return is_wall;
}
};
~~~
**Java 选手幻境生成器类：**
~~~java
class MazeGenerator {
private long seed;
private int n, m, p, sx, sy, ex, ey;
private int current_i, current_j;
private long next_rand() {
seed = (seed * 1103515245L + 12345L) & 0xFFFFFFFFL;
return (seed / 65536L) % 32768L;
}
public MazeGenerator(int n, int m, int p, int sx, int sy, int ex, int ey, long seed) {
this.n = n; this.m = m; this.p = p;
this.sx = sx; this.sy = sy; this.ex = ex; this.ey = ey;
this.seed = seed;
this.current_i = 1;
this.current_j = 1;
}
public int next_cell() {
if (current_i > n) return -1;
int is_wall = 0;
if (current_i == sx && current_j == sy) {
is_wall = 0;
} else if (current_i == ex && current_j == ey) {
is_wall = 0;
} else {
is_wall = (next_rand() % 100 < p) ? 1 : 0;
}
current_j++;
if (current_j > m) {
current_j = 1;
current_i++;
}
return is_wall;
}
}
~~~
请你帮栗山未来算出：从起点走到终点，最少需要花费多少时间？
如果终点被妖气彻底封死，永远无法到达，请输出 -1。
输入格式
输入仅包含一行，包含 8 个整数，依次为：
$N, M, P, sx, sy, ex, ey, Seed$
分别表示：迷宫的行数、列数、墙壁生成阈值（百分比）、起点行号、起点列号、终点行号、终点列号，以及秋人传递的初始灵力种子。
输出格式
输出一行一个整数，表示最少花费的时间。如果不可达，输出 -1。
说明/提示
请先实例化类对象，再调用类对象的成员函数生成网格图。
**数据范围：**
对于 100% 的数据：
* $1 ≤ N, M ≤ 3000$
* $0 ≤ P ≤ 100$
* $1 ≤ sx, ex ≤ N$
* $1 ≤ sy, ey ≤ M$
* $0 ≤ Seed ≤ 1000000000$