Description

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

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

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

Input

输入的第一行包含两个整数 \(n\) 和 \(m\), 分别表示行数和列数. 接下来是 \(2\) 个 \(n \times m\) 的自然数矩阵, 为 \(A_{i,j}\) 和 \(B_{i,j}\) 最后一行六个数, 分别代表 \(X, Y, Z\) 所在地的行号和列号.

Output

第一行输出一个字符 \(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

Data Range

对于 100% 的数据, 满足:\(1 \leq n, m \leq 150, 0 \leq q_{i,j} \leq 10^9, 0 \leq b_{i,j} \leq 1000\)

Explanation

由于我们只有三个可能终点, 所以我们只需要清楚以这三个点为终点分别的代价是多少就可以 完成此题了.

直接上一个 堆优化的 Dijkstra, 搞定......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define minimize(__x,__y) __x=min(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 210, maxk = 310;
const int infinit = 0x3fffffff;
const int movx[5] = {  0,  0,  1, -1,  0 },
          movy[5] = {  1, -1,  0,  0,  0 };

struct pnt { int x, y, w, s;
    pnt(int _1, int _2, int _3, int _4) { x = _1, y = _2, w = _3, s = _4;
        return ;}
}; bool operator < (pnt a, pnt b) {
    return a.w > b.w; }

int n, m, mx, x1, x2, x3, y1, y2, y3;
int a[maxn][maxn], b[maxn][maxn];
int dist[maxn][maxn][maxk];
bool vis[maxn][maxn][maxk];

void dijkstra(int beg_x, int beg_y)
{
    priority_queue<pnt> pq;
    rep(i, 1, n) rep(j, 1, m) rep(k, 0, mx) {
        vis[i][j][k] = false;
        dist[i][j][k] = infinit;
    }
    vis[beg_x][beg_y][0] = true;
    dist[beg_x][beg_y][a[beg_x][beg_y]] = b[beg_x][beg_y];
    pq.push(pnt(beg_x, beg_y, b[beg_x][beg_y], a[beg_x][beg_y]));
    while (!pq.empty() && (!vis[x1][y1][0] || !vis[x2][y2][0] || !vis[x3][y3][0])) {
        pnt pr = pq.top(); pq.pop();
        int x = pr.x, y = pr.y, w = pr.w, s = pr.s;
        if (vis[x][y][s]) continue;
        vis[x][y][s] = true;
        if (s > 0) {
            rep(k, 0, 4) {
                int nx = x + movx[k], ny = y + movy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if (vis[nx][ny][s-1]) continue;
                if (dist[x][y][s] < dist[nx][ny][s-1]) {
                    dist[nx][ny][s-1] = dist[x][y][s];
                    pq.push(pnt(nx, ny, dist[nx][ny][s-1], s-1));
                }
            }
        } else {
            int t = a[x][y];
            if (dist[x][y][t] > dist[x][y][0] + b[x][y]) {
                dist[x][y][t] = dist[x][y][0] + b[x][y];
                pq.push(pnt(x, y, dist[x][y][t], t));
            }
        }
    }
    // Cleanup operations
    while (!pq.empty())
        pq.pop();
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    mx = n + m - 2;
    rep(i, 1, n) rep(j, 1, m)
        scanf("%d", &a[i][j]);
    rep(i, 1, n) rep(j, 1, m)
        scanf("%d", &b[i][j]);
    // Setting minimum on cost
    rep(i, 1, n) rep(j, 1, m)
        minimize(a[i][j], max(mx-i-j, i+j-2));
    // Now proceeding with dijkstra (heaped)
    scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
    int a1, a2, b1, b2, c1, c2;
    dijkstra(x1, y1); a1 = dist[x2][y2][0], a2 = dist[x3][y3][0];
    dijkstra(x2, y2); b1 = dist[x1][y1][0], b2 = dist[x3][y3][0];
    dijkstra(x3, y3); c1 = dist[x1][y1][0], c2 = dist[x2][y2][0];
    // Tempting shortest path
    int mn = infinit;
    char res = '-';
    if (b1 + c1 < mn) mn = b1 + c1, res = 'X';
    if (a1 + c2 < mn) mn = a1 + c2, res = 'Y';
    if (a2 + b2 < mn) mn = a2 + b2, res = 'Z';
    if (mn >= infinit)
        printf("NO\n");
    else
        printf("%c\n%d\n", res, mn);
    return 0;
}