小红的皇后

[题目链接](https://www.nowcoder.com/practice/32b1af25432c4774b353c9d628dd9efb)

思路

棋盘上有一个皇后，从左上角 $(1,1)$ 出发，每一步可以沿着右、下、右下对角线三个方向移动任意多格（中途不能越过障碍物），问到达右下角 $(n,m)$ 的最少步数。

这和普通 BFS 有什么区别？

普通网格 BFS 每次只走一格，而这里一步可以"滑行"整条直线。如果暴力地把每个可达格子都当作一条边来建图，边数可达 $O(n \cdot m \cdot (n+m))$ ，会超时。

关键优化：沿射线扩展时的剪枝

用标准 BFS 逐层搜索，每次取出一个格子 $(x,y)$ ，设其距离为 $d$ ，然后沿三个方向一格一格向外探测。对于探测到的格子 $(nx, ny)$ ：

未访问过（ $dist = -1$ ）：设置距离为 $d+1$ ，加入队列，继续向外探测；
已访问且 $dist \leq d$ ：说明这个格子在之前的层已经被处理过，从它出发能到达的格子也已经被更早地探索过了——沿着同一方向继续探测不可能找到更优解，直接 break；
已访问且 $dist = d+1$ ：这个格子和当前格子在同一层或下一层，虽然不需要再次入队，但沿同方向更远处可能还有未访问的格子，所以继续探测。

为什么情况 2 可以安全地 break？因为 $dist[nx][ny] \leq d$ 意味着 $(nx,ny)$ 在更早的 BFS 层就被发现了。从 $(nx,ny)$ 继续沿同方向走能到达的格子，在处理 $(nx,ny)$ 时就已经被扩展过了（距离为 $dist[nx][ny]+1 \leq d+1$ ），不会比当前路径更差。所以继续探测没有意义。

这个剪枝保证了每个格子在每个方向上最多被跳过一次，总时间复杂度控制在 $O(n \cdot m)$ 级别。

样例演示

以样例 2 为例， $3 \times 4$ 的棋盘：

....
**.*
....

从 $(0,0)$ 出发，向右可达 $(0,1), (0,2), (0,3)$ ，向下被障碍挡住，对角线也被挡住。这些格子距离都是 1。
从 $(0,3)$ 出发，向下到 $(1,3)$ （被障碍挡住， $grid[1][3]=$ .，可以到达），再到 $(2,3)$ ，距离为 2。

所以答案是 $2$ ：先向右滑到 $(0,3)$ ，再向下滑到 $(2,3)$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for(int i = 0; i < n; i++) cin >> grid[i];

    vector<vector<int>> dist(n, vector<int>(m, -1));
    dist[0][0] = 0;
    deque<pair<int,int>> dq;
    dq.push_back({0, 0});

    int dx[] = {0, 1, 1};
    int dy[] = {1, 0, 1};

    while(!dq.empty()){
        auto [x, y] = dq.front();
        dq.pop_front();
        int d = dist[x][y];

        for(int dir = 0; dir < 3; dir++){
            for(int step = 1; ; step++){
                int nx = x + dx[dir] * step;
                int ny = y + dy[dir] * step;
                if(nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '*') break;
                if(dist[nx][ny] == -1){
                    dist[nx][ny] = d + 1;
                    dq.push_back({nx, ny});
                } else if(dist[nx][ny] <= d){
                    break;
                }
            }
        }
    }

    cout << dist[n-1][m-1] << "\n";
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = br.readLine().toCharArray();
        }

        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, -1);
        dist[0][0] = 0;
        Deque<int[]> dq = new ArrayDeque<>();
        dq.addLast(new int[]{0, 0});

        int[] dx = {0, 1, 1};
        int[] dy = {1, 0, 1};

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int x = cur[0], y = cur[1];
            int d = dist[x][y];

            for (int dir = 0; dir < 3; dir++) {
                for (int step = 1; ; step++) {
                    int nx = x + dx[dir] * step;
                    int ny = y + dy[dir] * step;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '*') break;
                    if (dist[nx][ny] == -1) {
                        dist[nx][ny] = d + 1;
                        dq.addLast(new int[]{nx, ny});
                    } else if (dist[nx][ny] <= d) {
                        break;
                    }
                }
            }
        }

        System.out.println(dist[n - 1][m - 1]);
    }
}

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())

    dist = [[-1]*m for _ in range(n)]
    dist[0][0] = 0
    dq = deque()
    dq.append((0, 0))

    dx = [0, 1, 1]
    dy = [1, 0, 1]

    while dq:
        x, y = dq.popleft()
        d = dist[x][y]
        for dir in range(3):
            step = 1
            while True:
                nx = x + dx[dir] * step
                ny = y + dy[dir] * step
                if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] == '*':
                    break
                if dist[nx][ny] == -1:
                    dist[nx][ny] = d + 1
                    dq.append((nx, ny))
                elif dist[nx][ny] <= d:
                    break
                step += 1

    print(dist[n-1][m-1])

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const grid = [];
    for (let i = 1; i <= n; i++) grid.push(lines[i]);

    const dist = Array.from({length: n}, () => new Int32Array(m).fill(-1));
    dist[0][0] = 0;
    const dq = [[0, 0]];
    let head = 0;

    const dx = [0, 1, 1];
    const dy = [1, 0, 1];

    while (head < dq.length) {
        const [x, y] = dq[head++];
        const d = dist[x][y];
        for (let dir = 0; dir < 3; dir++) {
            for (let step = 1; ; step++) {
                const nx = x + dx[dir] * step;
                const ny = y + dy[dir] * step;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] === '*') break;
                if (dist[nx][ny] === -1) {
                    dist[nx][ny] = d + 1;
                    dq.push([nx, ny]);
                } else if (dist[nx][ny] <= d) {
                    break;
                }
            }
        }
    }

    console.log(dist[n-1][m-1]);
});

复杂度分析

时间复杂度： $O(n \cdot m)$ 。每个格子入队一次，且在每个方向上至多被"路过"一次（被 break 剪枝掉），总探测次数为 $O(n \cdot m)$ 。
空间复杂度： $O(n \cdot m)$ 。存储棋盘和距离数组。