面试高频图论题『墙与门』：Swift BFS 解法全流程拆解

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • Swift 代码如下：
    • 示例测试及结果
    • 时间复杂度
    • 空间复杂度
    • 总结
    • 可运行 Demo 模块（Xcode Playground）
    • 参考场景与拓展

      摘要

      在日常开发中，我们经常遇到图遍历、路径规划的问题，特别是涉及二维网格的场景。LeetCode 第 286 题《墙与门》就非常贴近现实，比如模拟房间内路径计算、楼层距离评估等。本文将通过 Swift 语言，用广度优先搜索（BFS）方式一步步拆解这个问题，并给出一套完整的可运行 Demo 和测试用例，帮你在刷题和实际项目中都能用得上。

      

      描述

      题目大致是这样的：

      你有一个二维网格，表示一栋建筑的布局。每个格子可以是三种之一：

      • 墙（-1）：表示这个格子不能通行；
      • 门（0）：表示你从这出发是免费的；
      • 空房间（INF）：表示你需要计算从最近的门到这里的最短距离。

        你要做的就是把所有空房间都填上到最近门的距离。如果一个空房间无法到达任何门，保持 INF 不变。

        特别注意：

        这个问题要求在原数组上原地修改。

        

        题解答案

        我们最直观的思路是，对于每一个空房间，去找离它最近的门。但这样做效率非常低，因为每个空房间都要遍历一次地图。

        更优的解法是：从所有门开始做 BFS，因为 BFS 本质上就是按层级扩散的，最先访问到某个点的路径就是最短路径。

        题解代码分析

        Swift 代码如下：

        import Foundation
        let INF = Int(Int32.max)
        func wallsAndGates(_ rooms: inout [[Int]]) {
            let m = rooms.count
            let n = rooms[0].count
            var queue: [(Int, Int)] = []
            // 找出所有的门（0），作为 BFS 的起点
            for i in 0..
                for j in 0..
                    if rooms[i][j] == 0 {
                        queue.append((i, j))
                    }
                }
            }
            let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            while !queue.isEmpty {
                let (row, col) = queue.removeFirst()
                for dir in directions {
                    let newRow = row + dir.0
                    let newCol = col + dir.1
                    // 如果是有效的空房间，则更新并加入队列
                    if newRow = 0, newRow  
        示例测试及结果
         
        我们构造一个简单的输入样例来看下效果：
         
        var rooms = [
            [INF,  -1,    0,  INF],
            [INF, INF,  INF,  -1],
            [INF,  -1,  INF,  -1],
            [0,    -1,  INF, INF]
        ]
        wallsAndGates(&rooms)
        for row in rooms {
            print(row)
        }
         
        输出结果：
         
        [3, -1, 0, 1]
        [2, 2, 1, -1]
        [1, -1, 2, -1]
        [0, -1, 3, 4]
         
        可以看到，每个空房间都被填上了到最近门的距离，而且墙和门保持不变。非常贴近现实中路径计算场景。
         
        时间复杂度
         
        

        • O(m × n)：每个格子最多只被访问一次，所以整体复杂度和地图大小成正比。

          空间复杂度

          • O(m × n)：最坏情况下，队列中会放入所有空房间。

            总结

            这个题虽然看起来简单，但其实考察了你对 BFS 的理解。你需要反过来思考 —— 不是从目标找路径，而是从“源头”出发，让最短路径自己扩散。

            这和现实生活中很多问题非常像，比如：

            • 最短配送路径（从仓库到客户）
            • 电梯调度系统（从最近楼层开始响应）
            • 消防路径规划（从灭火点扩散）

              可运行 Demo 模块（Xcode Playground）

              你可以将以下代码粘贴到 Xcode 的 Playground 中运行：

              import Foundation
              let INF = Int(Int32.max)
              func wallsAndGates(_ rooms: inout [[Int]]) {
                  let m = rooms.count
                  let n = rooms[0].count
                  var queue: [(Int, Int)] = []
                  for i in 0..
                      for j in 0..
                          if rooms[i][j] == 0 {
                              queue.append((i, j))
                          }
                      }
                  }
                  let directions = [(0,1), (1,0), (0,-1), (-1,0)]
                  while !queue.isEmpty {
                      let (row, col) = queue.removeFirst()
                      for dir in directions {
                          let newRow = row + dir.0
                          let newCol = col + dir.1
                          if newRow = 0, newRow  
              参考场景与拓展
               
              这种解法在很多游戏开发、智能交通系统、路径推荐算法中都能派上用场。例如：
               
              

              • 游戏角色自动寻路系统（从多个终点扩散路径）
              • 城市中电动车租赁系统推荐最近的还车点
              • 超市货架路径优化（最近收银通道）