智能机器人

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

思路

本题是经典的迷宫最短路径问题：在 $n \times m$ 的网格中，从起点 s 到终点 e，每次可以上下左右移动一步，# 不可通行，求最少步数，不可达输出 $-1$ 。

为什么用 BFS？

每一步的代价都是 $1$ （无权图），BFS 天然保证第一次到达某个格子时的步数就是最短步数。这是 BFS 的核心性质：按层扩展，层数即距离。

具体做法

遍历网格，找到起点 s 和终点 e 的坐标。
用一个 $n \times m$ 的距离数组 dist，初始化为 $-1$ （表示未访问），将起点距离设为 $0$ 并入队。
BFS 逐层扩展：取出队首 $(x, y)$ ，尝试四个方向 $(nx, ny)$ ，若在边界内、不是墙、且未访问过，则 dist[nx][ny] = dist[x][y] + 1，入队。
当队首就是终点时，直接输出距离并结束。若队列为空仍未到达终点，输出 $-1$ 。

复杂度分析

时间复杂度： $O(n \times m)$ ，每个格子最多入队一次。
空间复杂度： $O(n \times m)$ ，距离数组和队列的开销。

代码

C++
Java
Python3
JavaScript

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

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<string> grid(n);
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 's') { sx = i; sy = j; }
            if (grid[i][j] == 'e') { ex = i; ey = j; }
        }
    }
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int,int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == ex && y == ey) {
            printf("%d\n", dist[x][y]);
            return 0;
        }
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    printf("-1\n");
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        char[][] grid = new char[n][m];
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 's') { sx = i; sy = j; }
                if (grid[i][j] == 'e') { ex = i; ey = j; }
            }
        }
        int[][] dist = new int[n][m];
        for (int[] row : dist) Arrays.fill(row, -1);
        Queue<int[]> q = new LinkedList<>();
        dist[sx][sy] = 0;
        q.add(new int[]{sx, sy});
        int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            if (x == ex && y == ey) {
                System.out.println(dist[x][y]);
                return;
            }
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '#' && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.add(new int[]{nx, ny});
                }
            }
        }
        System.out.println(-1);
    }
}

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    m = int(input_data[idx]); idx += 1
    grid = []
    sx = sy = ex = ey = 0
    for i in range(n):
        row = input_data[idx]; idx += 1
        grid.append(row)
        for j in range(m):
            if row[j] == 's':
                sx, sy = i, j
            elif row[j] == 'e':
                ex, ey = i, j
    dist = [[-1] * m for _ in range(n)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    while q:
        x, y = q.popleft()
        if x == ex and y == ey:
            print(dist[x][y])
            return
        for dx, dy in ((0,1),(0,-1),(1,0),(-1,0)):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] != '#' and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    print(-1)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m] = lines[0].split(' ').map(Number);
    const grid = [];
    let sx = 0, sy = 0, ex = 0, ey = 0;
    for (let i = 0; i < n; i++) {
        grid.push(lines[i + 1]);
        for (let j = 0; j < m; j++) {
            if (grid[i][j] === 's') { sx = i; sy = j; }
            if (grid[i][j] === 'e') { ex = i; ey = j; }
        }
    }
    const dist = Array.from({length: n}, () => new Array(m).fill(-1));
    dist[sx][sy] = 0;
    const q = [[sx, sy]];
    let head = 0;
    const dx = [0, 0, 1, -1], dy = [1, -1, 0, 0];
    while (head < q.length) {
        const [x, y] = q[head++];
        if (x === ex && y === ey) {
            console.log(dist[x][y]);
            return;
        }
        for (let d = 0; d < 4; d++) {
            const nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] !== '#' && dist[nx][ny] === -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push([nx, ny]);
            }
        }
    }
    console.log(-1);
});