京东 · 图 · 算法编程题
京东 图 n ≤ 2000 时限 3 秒 / 256 MB

题目描述

有一个 n 行 m 列的棋盘，有一些格子是障碍物不能通过。小红控制一个皇后在从左上角出发，每次移动她可以控制皇后进行以下三种方式中的一种：
1. 向右移动若干个格子。
2. 向下移动若干个格子。
3，向右下移动若干个格子。
用数学语言描述，当前的坐标在 (x,y) 时，每次移动可以到 (x+k,y) 或 (x,y+k) 或 (x+k,y+k) ，其中 k 为任意正整数。移动的前提是，路径上没有障碍物。
小红想知道，皇后从左上角移动到右下角，最少要移动多少步？

输入输出

输入描述
第一行输入两个正整数 n 和 m ，代表行数和列数。
接下来的 n 行，每行输入一个长度 m 的字符串，用来表示棋盘。
其中'.'代表可以通过的位置，'*'代表障碍物。
保证左上角和右下角都不是障碍物。
1≤ n,m ≤ 2000
输出描述
如果无法到达，请输出-1。
否则输出一个整数，代表最少的移动次数。

样例共 2 组

样例 1
输入
3 3
...
.**
.*.
输出
-1
样例 2
输入
3 4
....
**.*
....
输出
2

算法解析依据充分

考点：图 · 广度优先搜索(BFS) · 并查集

数据规模 n ≤ 2000 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 2000，m ≤ 2000
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 n ≤ 2000，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。

样例

样例 1

  • 输入：3 3 / ... / .** / .*.
  • 输出：-1

样例 2

  • 输入：3 4 / .... / **.* / ....
  • 输出：2

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2023年秋招-京东-技术通用岗位-第二批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解