企业官网建设流程全解析

1. 从棋盘上的马说起：为什么广搜优化值得单独拎出来讲

国际象棋里的马走日字，这个规则大家都熟。但把马放到一个空棋盘上，让它从起点跳到终点，最少需要几步？这个问题看起来简单到不值一提，可一旦棋盘变大、询问次数变多，朴素广搜就会立刻暴露出它的短板。Knight Moves 这道题之所以被放在"广搜的优化技巧"这一章里当例题，恰恰是因为它表面上是一道入门级的 BFS 模板题，实际上却是一个绝佳的优化试验场——你可以在它身上把双向广搜、状态压缩、预处理打表、剪枝等一系列技巧挨个试一遍，而且每一步优化带来的收益都能用最直观的数字衡量出来。

我最初接触这道题的时候，想法很朴素：八个方向，队列一层层扩展，遇到终点就返回步数，收工。提交之后确实能过，但当我看到棋盘规模从 8×8 涨到 100×100、询问组数从 1 组涨到上千组的时候，同样的代码就开始吃力了。这时候你才会认真去想：广搜的"广"到底广在哪里，哪些扩展是必要的，哪些是可以提前算好、可以两头同时推进、可以靠数学直接跳过的。

这篇文章面向的是已经会写基础 BFS、但还没系统整理过优化手段的读者。我会以 Knight Moves 为主线，把每一步优化的动机、原理、代码实现和实测效果都摊开讲清楚。你不需要有竞赛背景，只要能看懂队列和数组，就能跟着把整套思路走一遍。文中所有代码都是可运行的完整片段，棋盘坐标、方向数组、边界判断这些细节我都会交代到位，避免你复制过去发现差一两个下标对不上。

先说清楚这道题的标准设定：给定一个 n×n 的棋盘，马从坐标 (x1, y1) 出发，问到 (x2, y2) 最少走几步。坐标通常从 0 开始编号，马走"日"字，也就是横跨两格、纵跨一格，或者反过来。八个方向分别是 (±1, ±2) 和 (±2, ±1)。如果起点和终点相同，答案是 0。这些是后面所有讨论的基础，先钉死。

2. 朴素 BFS 的骨架与它真正的性能瓶颈

2.1 一层层扩散的本质：队列里装的是什么

广搜的核心思想是"按步数分层扩展"。队列里存的是当前已经到达、但还没往外扩展的格子。每一轮，我们把队列里同一层的所有格子取出来，尝试往八个方向跳，跳到的合法且没访问过的格子就入队，作为下一层。因为我们是逐层处理的，所以第一次碰到终点时，走过的步数一定是最少的——这就是 BFS 能求最短路的根本原因。

用代码表达，骨架大概是这样：

from collections import deque def knight_moves(n, start, end): if start == end: return 0 dirs = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)] visited = [[False]*n for _ in range(n)] q = deque() q.append((start[0], start[1], 0)) visited[start[0]][start[1]] = True while q: x, y, d = q.popleft() for dx, dy in dirs: nx, ny = x+dx, y+dy if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]: if (nx, ny) == end: return d+1 visited[nx][ny] = True q.append((nx, ny, d+1)) return -1

这段代码逻辑没问题，但它有两个隐藏的成本。第一，visited是一个 n×n 的布尔数组，每次询问都要重新初始化，n 大的时候这个初始化本身就是 O(n²)。第二，队列里每个元素都带着步数 d，内存占用翻倍。这两点在单次询问、小棋盘上无所谓，可一旦题目变成"多组询问"，它们就成了主要开销。

2.2 单次询问下朴素 BFS 到底慢在哪

我们做个粗略的复杂度分析。棋盘有 n² 个格子，最坏情况下 BFS 要把所有格子都访问一遍，每个格子扩展 8 个方向，所以单次询问的时间是 O(8n²)，也就是 O(n²)。对于 n=8 的经典棋盘，这只