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

摘要

在日常开发中，我们经常遇到图遍历、路径规划的问题，特别是涉及二维网格的场景。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..<m {
        for j in 0..<n {
            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 < m, newCol >= 0, newCol < n, rooms[newRow][newCol] == INF {
                rooms[newRow][newCol] = rooms[row][col] + 1
                queue.append((newRow, newCol))
            }
        }
    }
}

示例测试及结果

我们构造一个简单的输入样例来看下效果：

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..<m {
        for j in 0..<n {
            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 < m, newCol >= 0, newCol < n, rooms[newRow][newCol] == INF {
                rooms[newRow][newCol] = rooms[row][col] + 1
                queue.append((newRow, newCol))
            }
        }
    }
}

// 测试
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)
}

参考场景与拓展

这种解法在很多游戏开发、智能交通系统、路径推荐算法中都能派上用场。例如：

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