首页 > 试题广场 >

小红的皇后

[编程题]小红的皇后
  • 热度指数:114 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
有一个nm列的棋盘,有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发,每次移动她可以控制皇后进行以下三种方式中的一种:
1. 向右移动若干个格子。
2. 向下移动若干个格子。
3,向右下移动若干个格子。
用数学语言描述,当前的坐标在(x,y)时,每次移动可以到(x+k,y)(x,y+k)(x+k,y+k),其中k为任意正整数。移动的前提是,路径上没有障碍物。
小红想知道,皇后从左上角移动到右下角,最少要移动多少步?

输入描述:
第一行输入两个正整数nm,代表行数和列数。
接下来的n行,每行输入一个长度m的字符串,用来表示棋盘。
其中'.'代表可以通过的位置,'*'代表障碍物。
保证左上角和右下角都不是障碍物。
1\leq n,m \leq 2000


输出描述:
如果无法到达,请输出-1。
否则输出一个整数,代表最少的移动次数。
示例1

输入

3 3
...
.**
.*.

输出

-1
示例2

输入

3 4
....
**.*
....

输出

2

这道题你会答吗?花几分钟告诉大家答案吧!