该题作为 haha Round 2 比赛 T1。

题目背景

wyc 打开了自己最喜欢的游戏。

Minecraft，启动！

题目描述

wyc 一打开游戏，就发现自己被困在一个巨大的时空裂隙中（这就是模组的力量吗）。裂隙可以看作一个 $n \times m$ 的二维网格 $a$。$a_{i,j}$ 可能是：

• 基础类型：

  • .：空地，可自由通行。

  • #：基岩，不可破坏。

  • *：时空扭曲点，触发后会改变相邻格子的属性，详见“动态属性”。

• 动态属性：

  1. 当移动到 * 所在格时，可以固定 *，需要消耗 1 点饱腹值。固定后 * 不再旋转。

  2. 每次移动到 * 所在格，此格如果未被固定，会按顺时针方向旋转周围几格的基础类型。

  3. 注意这里表述的优先级。

wyc 从 $(1,1)$ 出发，目标是到达 $(n,m)$。移动规则如下：

1. 每次只能向上、下、左、右四个方向移动。

2. 每次移动后，所有未被固定的 * 都会触发旋转

3. 饱腹值初始为 $k$，即最多可固定 $k$ 次时空扭曲点

求在能量不耗尽的前提下，wyc 能否到达 $(n,m)$？
若能，输出最小步数；否则输出 -1。

输入格式

第一行三个整数 $n,m,k$。

接下来 $n$ 行，每行 $m$ 个字符，描述网格。

输出格式

输出最小步数。若不能到达 $(n,m)$ 输出 -1。

输入输出样例

3 3 0
.*#
*.*
.*.

4

说明/提示

样例解释

1. $(1,1) \to (1,2)$，无法固定（饱腹值不足），发生旋转，网格变为：

   .*.
   *#*
   .*.
   

2. $(1,2) \to (1,3)$。

3. $(1,3) \to (2,3)$，无法固定。网格变为：

   .*#
   *.*
   .*.
   

4. $(2,3) \to (3,3)$。抵达终点，最小步数为 $4$。

数据范围与约定

对于 $100\%$ 的数据，$1 \le n,m \le 20,0 \le k \le 5$。

保证起点和终点不是基岩。