240913 - 星际跃迁的最优能量补充

题目描述

在遥远的宇宙中,有 n * m 个星际站点,每个站点由两种能量类型组成:'X''Y'。宇航员每次到达一个站点时,需要补充能量,补充规则如下:

  • 如果到达的站点能量类型为 'X',则需要消耗 300 费用。
  • 如果到达的站点能量类型为 'Y',则需要消耗 700 费用。

宇航员可以从一个站点跃迁到相邻的上下左右四个站点。给定起点和终点坐标,请计算从起点到终点的最小总能量补充费用。注意:起点和终点也需要补充能量。

输入

输入的第一行是两个整数 nm,表示星际站点的行数和列数(1 ≤ n, m ≤ 500)。
接下来的 n 行,每行包含 m 个字符('X''Y' ),表示每个站点的能量类型。
最后一行包含四个整数 x1, y1, x2, y2,表示起点和终点的坐标(行列从 1 开始编号)。

输出

输出一个整数,表示从起点到终点的最小总能量补充费用。

样例

输入

3 3
XYX
YXY
XYX
1 1 3 3

输出

2300

输入

4 6
XYXYXY
YYYYYY
XXYYYX
XYYXXX
1 4 4 1

输出

3300
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 34
通过人数 19
金币数量 2 枚
难度 基础


上一题 下一题