Skip to content

12106: 【原2106】二哥的逃离

题目

题目描述

author: Swrrt_11 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2106

Description

二哥突然学会了Blink(闪烁)魔法,但他也因此被伊利丹追杀。在慌乱之间,二哥冲入了迷宫的入口,被传送进入了远古之迷宫。

“你将一分为三,两个分身,一个本体。分身不能走动只能使用魔法,而本体则会被束缚而完全无法动弹,他们会被传送至不同的地方。但是作为补偿,你可以在开始行动之前,决定自己的本体是三者中的哪一个。当三者重新汇聚,束缚将被打破,你也自然脱离了迷宫。”二哥在恍惚之间听到了这样一番话。

迷宫是一个矩形,被划分成了\( N \)行\( M \)列共\(N \times M\)个小格。迷宫左上角小格的坐标定义为\((1,1)\),右上角小格的坐标定义为\((1,M)\),右下角小格的坐标定义为\((N,M)\)。两小格\((a,b)\),\((c,d)\)之间的距离定义为\(|a-c|+|b-d|\)(即曼哈顿距离)。

二哥唯一能做的事就是使用闪烁魔法,来使得自己的两个分身尽快与本体会合。不过正如同之前听到的那句话,只有分身能够使用闪烁魔法进行移动。

由于二哥的魔法水平有限,他每次使用魔法只能让分身移动到一定距离以内的任意一个小格并且在进行移动之前需要一段时间进行准备(吟唱魔法)。而在这个神秘的迷宫里,二哥发现他的分身在每个小格所能移动的距离和吟唱时间是不同的。

在 \( (i,j) \)小格上能移动的最大距离为: \( A_{i,j} \)

需要的准备时间为: \( B_{i,j} \)

更加悲剧的是,二哥每次只能让一个分身进行吟唱魔法并移动,移动完毕之后才能进行下一次吟唱。

现在,二哥想知道,自己至少要花多少时间才能逃脱出迷宫。

注意:迷宫的外部是虚无,二哥不会通过闪烁移动到迷宫之外。

Input Format

第一行两个整数\( N,M \)

接下来两个\( N \times M \) 的自然数矩阵: \( A_{i,j} \) , \( B_{i,j} \)

接下来六个数\(Xx,Xy,Yx,Yy,Zx,Zy\),表示本体和两个分身的坐标。

Output Format

输出两行第一行一个字符\( X,Y\)或\( Z \),表示以哪一个为本体。

第二行一个整数,表示最短时间。

若无法逃出迷宫,则只输出一行"NO"(不带引号)。

Sample Input

4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2

Sample Output

Z
15

About Test Data

对于20%的数据:\( 1 \leq n,m \leq 10 \)。

对于50%的数据:\( 1 \leq n,m \leq 100 \) \( 1 \leq B_{i,j} \leq 30 \)。

对于100%的数据:\( 1 \leq n,m \leq 100 \)

\( 1 \leq B_{i,j} \leq 100 \)

\( 1 \leq A_{i,j} \leq 10^9 \)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!