首页 > 试题广场 >

小红的皇后

[编程题]小红的皇后
  • 热度指数: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
头像 丨阿伟丨
发表于 2025-09-16 17:39:20
题目链接 小红的皇后 题目描述 在一个 的棋盘上,小红的皇后从左上角 (0,0) 出发,要到达右下角 (n-1, m-1)。有些格子是障碍物。 皇后每次可以向右、下或右下移动任意多个格子,但移动的路径上不能有障碍物。求从起点到终点的最少移动次数。如果无法到达,输出 -1。 解题思路 这是一个在网格 展开全文
头像 Silencer76
发表于 2025-04-01 17:34:33
题目链接 小红的皇后 题目描述 有一个 的棋盘,有一些格子是障碍物不能通过。小红控制一个皇后从左上角出发,每次移动她可以控制皇后进行以下三种方式中的一种: 向右移动若干个格子 向下移动若干个格子 向右下移动若干个格子(斜向移动) 移动的前提是路径上没有障碍物。小红想知道,皇后从左上角移动到右下 展开全文