AT_joi2011yo_e.チーズ (Cheese)

今年 JOI 镇的奶酪工厂又开始生产奶酪了，老鼠也从巢穴里探出了头。JOI 镇按照东西南北的方向被划分为若干区块，每个区块要么是巢穴、奶酪工厂、障碍物，或者空地。老鼠从巢穴出发，必须访问所有奶酪工厂，并且每到一个工厂吃掉 $1$ 个奶酪。

这个镇上有 $N$ 个奶酪工厂，每个工厂只生产一种奶酪。不同工厂生产的奶酪硬度各不相同，分别为 $1$ 到 $N$，每种硬度的奶酪工厂各有一个。

老鼠的初始体力为 $1$，每吃掉 $1$ 个奶酪体力就增加 $1$。但是，老鼠不能吃比自己体力更硬的奶酪。

老鼠每次可以用 $1$ 分钟移动到东西南北相邻的区块，但不能进入障碍物区块。老鼠可以经过奶酪工厂而不吃奶酪。请编写程序，求老鼠吃完所有奶酪所需的最短时间。吃奶酪所需的时间可以忽略不计。

输入共 $H+1$ 行。第 $1$ 行包含三个整数 $H, W, N$（$1 \leq H \leq 1000$，$1 \leq W \leq 1000$，$1 \leq N \leq 9$），用空格隔开。第 $2$ 行到第 $H+1$ 行，每行包含 $W$ 个字符，字符集为 S、1、2、$\ldots$、9、X、.，分别表示各区块的状态。若将北边第 $i$ 行、西边第 $j$ 列的区块记为 $(i, j)$（$1 \leq i \leq H$，$1 \leq j \leq W$），则第 $i+1$ 行第 $j$ 个字符表示区块 $(i, j)$ 的状态：S 表示巢穴，X 表示障碍物，. 表示空地，1、2、$\ldots$、9 表示生产硬度为 $1$、$2$、$\ldots$、$9$ 的奶酪的工厂。输入保证巢穴和每种硬度的奶酪工厂各有一个，其他区块为障碍物或空地。保证老鼠一定能吃到所有奶酪。

输出一个整数，表示老鼠吃完所有奶酪所需的最短时间（分钟数）。

样例解释 1

- - - - - -

样例解释 2

- - - - - -

由 ChatGPT 4.1 翻译