贝壳找房 · 广度优先搜索(BFS) · 算法编程题
贝壳找房 广度优先搜索(BFS) 时限 1 秒 / 256 MB

题目描述

牛可乐有一个 H 行 M 列的迷宫，如果 S_i,j 是'#',代表第 i 行第 j 列的方格为墙壁，如果 S_i,j 是'.',代表第 i 行第 j 列的方格为可走方格。 每一步移动在一个可走方格，可以水平的或者垂直的移动到相邻的一个可走方格中。
但是不能走出迷宫，不能走到一个墙壁方格，也不能对角线方向移动。
你可以选择任意一个起点方格和终点方格（这两个方格必须为可走方格，且可以相互到达）。
牛可乐将从你选择的起点方格用最小的步数移动到终点方格。
本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大，你需要计算这个步数的最大值。

输入输出

输入描述
第一行一个整数 H,W(1 ≤ H,W ≤ 60)
接下来 n 行，每行 m 个字符 代表迷宫 S
S 中至少包含2个字符‘.’
输出描述
一行一个整数代表答案

样例共 3 组

样例 1
输入
3 3
...
.#.
...
输出
4
样例 2
输入
5 5
...#.
...#.
.#...
#....
.#..#
输出
8
样例 3
输入
5 5
#..#.
...#.
.....
#.#..
....#
输出
8

算法解析依据一般

考点：广度优先搜索(BFS)

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 元素值域：H ≤ 60，W ≤ 60（注意整数类型选择，避免溢出）
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：广度优先搜索(BFS)

按层扩散搜索，无权图上第一次到达即最短路。

思路框架（广度优先搜索(BFS) 通法 · 非本题专属）

  1. 起点入队并标记已访问。
  2. 每次取队首，把它的所有未访问邻居入队并记录步数。
  3. 第一次访问到目标时，步数即为最少步数。
  4. 网格类题目通常有 4（或 8）个方向，用方向数组统一处理。

实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。

复杂度：时间 O(V+E) ｜ 空间 O(V)

该范式的通法易错点

  • 出队才标记访问导致 MLE/TLE。
  • 网格边界没判，越界访问。

对照本题

  • 元素值域最大到 60 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：3 3 / ... / .#. / ...
  • 输出：4

样例 2

  • 输入：5 5 / ...#. / ...#. / .#... / #.... / .#..#
  • 输出：8

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

本题来源：贝壳找房2023届校招算法卷1。

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