题目链接

迷宫寻路

题目描述

给定一个 的矩形迷宫。每个格子要么是空地 .，要么是墙 #。只能在空地间按上下左右四个方向移动。起点为左上角 ，终点为右下角 。判断是否存在一条路径从起点到终点。

输入：

  • 第一行两个正整数 、
  • 接下来 行，每行一个长为 的仅包含 . 与 # 的字符串，表示迷宫
  • 保证起点与终点均为空地 .

输出：

  • 若可以到达终点，输出 Yes；否则输出 No

解题思路

典型网格可达性判定。采用宽度优先搜索（BFS）或深度优先搜索（DFS）均可。这里给出 BFS：

  • 用队列从起点 （以 0 基下标为 ）开始扩展
  • 每次从队头取出格子，对四个方向 尝试前进
  • 仅当新位置在边界内、且为 . 且未访问过时入队
  • 过程中一旦访问到 （0 基），即可返回可达

边界与实现要点：

  • 若起点或终点为墙（虽然题目保证不会），可直接输出 No
  • 使用访问标记避免重复入队

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) cin >> grid[i];

    if (grid[0][0] == '#' || grid[n - 1][m - 1] == '#') {
        cout << "No\n";
        return 0;
    }

    vector<vector<int>> visited(n, vector<int>(m, 0));
    queue<pair<int,int>> q;
    q.push(make_pair(0, 0));
    visited[0][0] = 1;
    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        pair<int,int> cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        if (x == n - 1 && y == m - 1) {
            cout << "Yes\n";
            return 0;
        }
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (visited[nx][ny]) continue;
            visited[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }

    cout << "No\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();
        int m = sc.nextInt();
        String[] grid = new String[n];
        for (int i = 0; i < n; i++) grid[i] = sc.next();

        if (grid[0].charAt(0) == '#' || grid[n - 1].charAt(m - 1) == '#') {
            System.out.println("No");
            return;
        }

        boolean[][] vis = new boolean[n][m];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0});
        vis[0][0] = true;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            if (x == n - 1 && y == m - 1) {
                System.out.println("Yes");
                return;
            }
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (grid[nx].charAt(ny) == '#') continue;
                if (vis[nx][ny]) continue;
                vis[nx][ny] = true;
                q.add(new int[]{nx, ny});
            }
        }
        System.out.println("No");
    }
}

from collections import deque

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

if grid[0][0] == '#' or grid[n - 1][m - 1] == '#':
    print('No')
else:
    vis = [[False] * m for _ in range(n)]
    q = deque([(0, 0)])
    vis[0][0] = True
    dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ok = False
    while q:
        x, y = q.popleft()
        if x == n - 1 and y == m - 1:
            ok = True
            break
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == '.' and not vis[nx][ny]:
                vis[nx][ny] = True
                q.append((nx, ny))
    print('Yes' if ok else 'No')

算法及复杂度

  • 算法：BFS/DFS 判定可达性
  • 时间复杂度：
  • 空间复杂度：（访问标记与队列在最坏情况下占用同量级）