SP11472 DCEPC701 - Amazing Maze

Chintu 和他的父亲 Nikka 在度假时去了一个名叫“神奇迷宫”的地方。但不幸的是，他们走散了，Nikka 必须尽快找到 Chintu，否则 Chintu 很快就会哭出来。 这个迷宫真如其名，充满着神奇之处！整个迷宫由一个矩形网格构成，网格中有墙壁（#）和可行走的空格（.）。你只能在空格中行走，不能跨越墙壁。奇妙的是，每堵墙在某个时刻都会变成可行走的空格（过渡时间可以忽略不计）。也就是说，某个时刻 $t1$ 时，墙壁会变成可行走的空格，这样你可以在时间 $t1$ **及之后的任何时间**穿过它。从一个空格只能移动到相邻的空格。相邻的格子指的是紧邻的上下左右四个方向的空格。每移动一次需要耗费 1 时间单位。此外，你还可以在一个空格上等待，直到它旁边的墙壁变成空格。 Nikka 手上有一张迷宫的地图，上面标注了每面墙变成可行走空格的时间。他还知道自己和 Chintu 各自所在的位置。请帮助 Nikka 计算出他需要多长时间才能找到他的儿子 Chintu。

第一行输入一个整数 $T$，表示有多少个测试用例。 每个测试用例的第一行包含两个整数 $M$ 和 $N$，表示迷宫的尺寸。 接下来的 $M$ 行，每行有 $N$ 个字符，只能是“#”或“.”，代表时间 $t=0$ 时迷宫的初始状态。 随后的 $M$ 行，每行有 $N$ 个非负整数。对应每个“.”，数值为 0；对应每个“#”，则是一个正整数，表示这堵墙变成可行走空格的时间。 接着一行输入两个整数 $x1$ 和 $y1$，表示 Nikka 在迷宫中的位置。 下一行输入两个整数 $x2$ 和 $y2$，表示 Chintu 在迷宫中的位置。

输出 $T$ 行，每行一个整数，表示 Nikka 到达 Chintu 所需的最短时间。

$$1 \le T \le 10$$ $$1 \le M, N \le 100$$ $$0 \le x1, y1, x2, y2 < M, N$$ **本翻译由 AI 自动生成**