题目描述

Tim 和 Tom 正在 Tim 家中玩一个叫作“超级门把手”的游戏。他们从房屋左上角出发，目标是尽快触碰指定数量的不同门把手。Tom 不熟悉 Tim 家的布局，因此需要你帮他计算最短路线长度。

房屋用一个字符网格表示：

• . 表示可以通行的空格；
• o 表示带有门把手的格子，第一次进入该格子时即触碰到这个门把手；
• # 表示墙壁，不能进入。

每一步只能向上、下、左、右移动一格，不能斜向移动。起点是左上角格子 $(1,1)$，且起点一定是空格。请求出至少触碰 $k$ 个不同门把手所需的最少移动步数。

如果无法从起点触碰到 $k$ 个不同门把手，输出 -1。

输入格式

第一行包含三个整数 $h,w,k$，分别表示网格行数、列数和需要触碰的门把手数量。

接下来 $h$ 行，每行一个长度为 $w$ 的字符串，表示房屋布局。

输出格式

输出至少触碰 $k$ 个不同门把手所需的最少移动步数；若无法完成，输出 -1。

样例 1

5 5 3
.....
o....
o....
o....
...o.

3

从起点连续向下移动三步即可依次触碰三个门把手。

样例 2

5 5 4
.....
o....
o....
o....
...o.

7

样例 3

5 5 1
.#...
#....
...oo
...oo
...oo

-1

起点被墙壁封住，无法到达任何门把手。

样例 4

5 5 4
...o.
o..o.
.....
..oo.
.....

7

样例 5

5 5 4
....#
.##o#
.##oo
o##.#
....#

12

样例 6

5 5 4
....#
o##o#
.##oo
.##.#
....#

8

数据范围与保证

• $5\le h,w\le50$；
• $1\le k\le4$；
• 网格只包含字符 ., o, #；
• 左上角格子一定是 .；
• 网格中的门把手数量在 $k$ 至 6 之间。