华为校招机试 - 矿车运输成本（20240522）

题目描述

露天矿采矿作业的特点是规模大，矿石和废料的移动量达到百万吨，运输成本开销较大，需要寻求一种最优的运输路径节省成本。

已知矿场可以划分成 N * M 的网格图，每个网格存在地形的差异，因此通过不同网格时，成本开销存在差异。

网格有以下 5 种类型：

1. 标志为 'S' 的网格为运输起点；
2. 标志为 'E' 的网格为运输终点；
3. 标志为 'B' 的网格为阻塞点，不允许通行；
4. 标志为 'C' 的网格为检查点，矿车在运输路径中，至少需要进入一次检查点。
5. 标志为 数字 的网格，其数字表示经过该网格的成本开销。

运输矿车只能上下左右 4 个方向运行，不允许斜对角进入其他网格。必要时可重复进入网格。

请根据输入的网格图，寻求一条从 S 网格到 E 网格，并且至少经过一次检查点的最低成本运输路径，并输出其成本开销。

输入描述

第一行：网格图的行数 N 和网格图的列数 M ，使用空格隔开。

• N 取值范围：[3，200]
• M 取值范围：[3，200]

第二行至第 N+1 行：网格图每一行的元素，可以为'S’，E’，'B'，‘C'或者数字[0,100]，并且有且仅有一个'S’和一个'E’，同时存在一个或者多个‘C'