在遥远的宇宙中,有 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