在遥远的宇宙中,有 n * m
个星际站点,每个站点由两种能量类型组成:'X'
和 'Y'
。宇航员每次到达一个站点时,需要补充能量,补充规则如下:
'X'
,则需要消耗 300 费用。'Y'
,则需要消耗 700 费用。宇航员可以从一个站点跃迁到相邻的上下左右四个站点。给定起点和终点坐标,请计算从起点到终点的最小总能量补充费用。注意:起点和终点也需要补充能量。
输入的第一行是两个整数 n
和 m
,表示星际站点的行数和列数(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