← 返回题目列表

AtCoder · joi2011yo_e

E. 奶酪

中文机器翻译题面 查看原题

配点: 100 点

問題

JOI镇的奶酪工厂今年又开始生产奶酪了,一只老鼠从窝里出来了。 JOI镇分为北、南、东、西四个部分,每个部分要么是巢穴,要么是奶酪工厂,要么是障碍物,要么是空地。老鼠离开巢穴,到所有的奶酪工厂去买奶酪。 1 一颗一颗地吃。

在这个小镇, 有N 个奶酪工厂,每个工厂都有 我们只生产 1 类型的奶酪。奶酪的硬度因工厂而异,硬度 生产奶酪高达 1 减去 N 的奶酪工厂 每个都有 1 。

鼠标初始体力为 1 和奶酪 1 每吃一个,你的健康就会增加。 1 增加。然而,老鼠不能吃比它的体力还硬的奶酪。

小鼠生活在北、南、东、西相邻的地块中。 您可以在 1 分钟内移动,但无法进入障碍物块。您甚至可以路过奶酪工厂而不吃任何奶酪。编写一个程序来找出吃完所有奶酪所需的最短时间。然而,老鼠吃掉奶酪所需的时间可以忽略不计。 有一条


入力

输入是 H+1 行。 直到1 在线 3 整数 H,W,N (1 \leqq H \leqq 1000,1 \leqq W \leqq 1000,1 \leqq N \leqq 9)按此顺序写入,并用空格分隔。 在2 从行 H + 1 行的每一行中, 第S,1,2,\ldots,9,X,. 组成 W 写入一串字符,每个字符代表每个部分的状态。从北方 i 个,从西边算起 第 j 个区块 记述为 (i, j) 。1 \leqq i \leqq H,1 \leqq j \leqq W),第 i + 1 线 j 个字符是分区 如果 (i, j) 是一个巢,那么 S ,如果它是一个障碍物, X ,如果是空地, . 和硬度 如果工厂生产 1,2,\ldots,9 奶酪, 1,2,\ldots,9 变为。输入的嵌套和硬度 每个生产 1,2,\ldots,N 奶酪的工厂 每个都有 1 。其他方块肯定是障碍物或空地。老鼠一定会吃掉所有的奶酪。

出力

一个整数,表示吃完所有奶酪所需的最短时间(以分钟为单位)。 输出为 1 请按行输出。


入力例 1

3 3 1
S..
...
..1

出力例 1

4

入力例 2

4 5 2
.X..1
....X
.XX.S
.2.X.

出力例 2

12

入力例 3

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

出力例 3

91