共享单车

共享单车

时间： 1ms        内存：128M

描述：

共享单车走进烟台，小明决定尝试。小明启动共享单车app，轻松地找到附近的单车。那么问题来了，到最近的那辆单车，小明大约要走多少米呢？
现在简化问题。将地图设定成一个由100米*100米的像素块组成的二维平面区域。如果一个方块内有单车，则像素块显示为字符“x”；如果此方块内是可以通行的路，则显示为“.”；再如果方块是建筑物，则显示为“*”，建筑物不能通行。
小明在地图上的位置显示为“o”，可以朝，“上”、“下”、“左”，“右”，“左上”，“左下”，“右上”，“右下”八个方向走。下图所示为一个小明站在像素方块O，如果小明向右走到X，则走100米；如果向右上走，则走141米（不需要开方）。
假设小明和单车都在方块的中央。现在给出 T 幅根据以上规则建立的地图，地图行数和列数分别为 n 和 m，请分别估算小明要走多少米才能到最近的单车？

如果计算中出现小数，那么直接舍弃。最后的输出的结果为整型。
给出的地图中至少有一辆单车，如果最终无法到达单车的位置，输出-1。

输入：

第1行，T，表示下面有 T 组测试数据
对于每组测试数据
（1）第1行，n和m ,表示地图的大小；
（2）第2行开始，给出具体的地图 。

输出：

T行数据
每行1个整数，表示问题的解

示例输入：

2
3 8
.....x..
.o...x..
........
8 10
.***......
.***......
.***..x...
..........
.....*****
..o..*****
.......x..
...*******

示例输出：

400
523

提示：

参考答案：

解锁文章

没有看到答案？微信扫描二维码可免费解锁文章

使用微信扫描二维码打开广告页面后可以立即关闭，再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供，并不代表本站观点！

已经扫描此二维码？点此立即跳转

文章解锁成功，即将自动跳转，点此立即跳转