首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路

热度指数：5784 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 旺仔哥哥被困在一个 $n\times m$ 的矩形迷宫里。每个格子要么是空地 (用符号 `.` 表示)，要么是墙 (用符号 `#` 表示)。旺仔哥哥只能从一个空地移动到其上下左右相邻的空地。
$\hspace{15pt}$ 已知旺仔哥哥的起点为左上角 $(1,1)$ ，终点为右下角 $(n,m)$ 。请判断他是否能够到达终点。

输入描述:

第一行输入两个正整数 。 
接下来的  行每行输入一个长为  的仅包含字符 `.` 与 `#` 的字符串，描述整个迷宫。 
保证起点  和终点  均为空地。

输出描述:

若旺仔哥哥可以走到终点，则输出单词 ；否则输出 。

示例1

输入

3 5
.##.#
.#...
...#.

输出

Yes

说明

路线如下：

算法知识视频讲解

Python3

牛客65283168号

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

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

def dfs(x, y):
    if x == n-1 and y == m-1:
        return True
    if not (0 <= x < n and 0 <= y < m and grid[x][y] == '.'):
        return False
    grid[x][y] = '#'          # 标记已访问
    for i in range(4):
        xx, yy = x + dx[i], y + dy[i]
        if 0 <= xx < n and 0 <= yy < m and grid[xx][yy] == '.':
            if dfs(xx, yy):
                return True
    return False

print('Yes' if dfs(0, 0) else 'No')

发表于 2026-01-19 21:38:16 回复(0)