Maze

题目描述

你收到一个迷宫。这是一个具有$𝑛$行和$𝑛$列的网格。行和列均从$1$到$𝑛$编号。第$𝑎$行和第$𝑏$列的交点用$(𝑎,𝑏)$表示。迷宫中的一些单元格是障碍物。最初，你站在左上角$(1,1)$。你的目标是到达右下角$(𝑛,𝑛)$。你可以从$(𝑎,𝑏)$向四个方向移动：向上到$(𝑎−1,𝑏)$、向下到$(𝑎+1,𝑏)$、向左到$(𝑎,𝑏−1)$或向右到$(𝑎,𝑏+1)$。你不能连续向同一方向移动超过$𝑚$步，不能离开网格，且带有障碍的单元格无法到达。到达$(𝑛,𝑛)$的最小步数是多少？

输入格式

输入由多个测试用例组成。第一行包含一个整数 $𝑡(1\leq t \leq 50)$测试用例的数量，测试用例的描述在后面。第一行包含两个整数$n,m$$(2\leq n \leq100,2\leq m \leq100)$，表示迷宫的大小和一次方向上最多可以进行的连续移动次数。接下来的$n$行描述迷宫。每行包含一个长度为 $𝑛$ 的字符串，只包含符号 $.$ 和 $*$。第$i$行的第 𝑗 个字符对应于迷宫中第 $𝑖$ 行第 $𝑗$ 列的格子。符号 $.$ 表示自由格子，而符号 $*$ 表示有障碍物的格子。

输出格式

对于每个测试用例，如果不可能到达 $(n,n)$，打印一个整数$-1$，否则打印最少的移动次数。

样例 #1

样例输入 #1

1
3 1
..*
..*
...

样例输出 #1

4