题目链接

智能机器人

题目描述

在一个 的迷宫中，机器人需要从起点 's' 走到终点 'e'。迷宫中 '.' 代表可通行的路径，'#' 代表障碍物。求机器人到达终点所需的最少步数。如果无法到达，则输出 -1。

解题思路

这是一个典型的在网格图中求解最短路径的问题。由于每一步的成本（权重）都相等（都为1），因此最适合使用广度优先搜索（Breadth-First Search, BFS） 算法。

BFS 的核心思想是从起点开始，像水波纹一样，一层一层地向外探索。它首先访问所有距离起点为 1 的节点，然后是所有距离为 2 的节点，以此类推。这个特性保证了当 BFS 第一次到达终点时，所经过的路径必然是最短的。

算法步骤如下：

  1. 初始化：

    • 创建一个队列，用于存放待访问的格子。队列中每个元素需要存储格子的坐标 (row, col) 和到达该格子的步数 steps。
    • 创建一个二维的 visited 数组，用于记录已经访问过的格子，防止重复访问和陷入死循环。
    • 遍历迷宫，找到起点 's' 的坐标，并将其作为第一个元素 (start_row, start_col, 0) 加入队列，同时在 visited 数组中标记为已访问。

  2. BFS 循环：

    • 当队列不为空时，从队列头部取出一个格子 (r, c, s)。
    • 如果这个格子是终点 'e'，则 s 就是最短步数，搜索结束。
    • 否则，检查该格子的上、下、左、右四个相邻格子。
    • 对于每个满足条件（在边界内、不是墙、未被访问过）的相邻格子，将其加入队列，并更新 visited 数组。新加入队列的格子的步数为 s + 1。

  3. 处理无解：

    • 如果队列为空时，仍未找到终点，则说明从起点无法到达终点，应输出 -1。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    int start_r, start_c;
    for (int i = 0; i < n; ++i) {
        cin >> maze[i];
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] == 's') {
                start_r = i;
                start_c = j;
            }
        }
    }

    queue<tuple<int, int, int>> q;
    q.emplace(start_r, start_c, 0);
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    visited[start_r][start_c] = true;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c, steps] = q.front();
        q.pop();

        if (maze[r][c] == 'e') {
            cout << steps << endl;
            return 0;
        }

        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && maze[nr][nc] != '#') {
                visited[nr][nc] = true;
                q.emplace(nr, nc, steps + 1);
            }
        }
    }

    cout << -1 << endl;

    return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] maze = new char[n][m];
        int startR = -1, startC = -1;

        for (int i = 0; i < n; i++) {
            maze[i] = sc.next().toCharArray();
            for (int j = 0; j < m; j++) {
                if (maze[i][j] == 's') {
                    startR = i;
                    startC = j;
                }
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startR, startC, 0});
        boolean[][] visited = new boolean[n][m];
        visited[startR][startC] = true;

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0];
            int c = current[1];
            int steps = current[2];

            if (maze[r][c] == 'e') {
                System.out.println(steps);
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && maze[nr][nc] != '#') {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc, steps + 1});
                }
            }
        }

        System.out.println(-1);
    }
}

import sys
from collections import deque

def solve():
    n, m = map(int, sys.stdin.readline().split())
    maze = [sys.stdin.readline().strip() for _ in range(n)]

    start_pos = None
    for r in range(n):
        for c in range(m):
            if maze[r][c] == 's':
                start_pos = (r, c)
                break
        if start_pos:
            break
    
    queue = deque([(start_pos[0], start_pos[1], 0)])
    visited = [[False for _ in range(m)] for _ in range(n)]
    visited[start_pos[0]][start_pos[1]] = True

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while queue:
        r, c, steps = queue.popleft()

        if maze[r][c] == 'e':
            print(steps)
            return

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]

            if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and maze[nr][nc] != '#':
                visited[nr][nc] = True
                queue.append((nr, nc, steps + 1))

    print(-1)

solve()

算法及复杂度

  • 算法：广度优先搜索 (BFS)
  • 时间复杂度：，其中 和 是迷宫的行数和列数。每个格子最多被访问一次。
  • 空间复杂度：，主要用于存储 visited 数组和队列。在最坏的情况下，队列可能需要存储所有可通行的格子。