配点: 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