bzoj#P2143. 飞飞侠

飞飞侠

题目描述

飞飞国是一个传说中的国度,国家的居民叫做飞飞侠。飞飞国是一个 N×MN\times M 的矩形方阵,每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第 ii 行第 jj 列的弹射装置有 AijA_{ij} 的费用和 BijB_{ij} 的弹射能力。并规定有相邻边的格子间距离是 11 。那么,任何飞飞侠都只需要在 (i,j)(i,j) 支付 AijA_{ij} 的费用就可以任意选择弹到距离不超过 BijB_{ij} 的位置了。如下图

在这里插入图片描述

(从红色街区交费以后可以跳到周围的任意蓝色街区。)

现在的问题很简单。有三个飞飞侠,分别叫做 XXYYZZ。现在它们决定聚在一起玩,于是想往其中一人的位置集合。告诉你 33 个飞飞侠的坐标,求往哪里集合大家需要花的费用总和最低。

输入格式

输入的第一行包含两个整数 NNMM ,分别表示行数和列数。接下来是 22N×MN\times M 的自然数矩阵,为 AijA_{ij}BijB_{ij} 最后一行六个数,分别代表 X,Y,ZX,Y,Z 所在地的行号和列号。

输出格式

第一行输出一个字符 X,YX,Y 或者 ZZ,表示最优集合地点。

第二行输出一个整数,表示最小费用。

如果无法集合,只输出一行 NO

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
Z
15

数据规模与约定

对于 100%100\% 的数据, 1N,M1501\le N, M \le 1500Aij1090 \le A_{ij} \le 10^90Bij1030\le B_{ij} \le 10^3