首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路

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

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

输入描述:

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

输出描述:

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

示例1

输入

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

输出

Yes

说明

路线如下：

算法知识视频讲解

学习小生

n , m = map(int,input().split())
arr = []
for i in range(n):
    arr.append(list(input()))
graph = {}
for i in range(n):
    for j in range(m):
        if arr[i][j] == ".":
            graph[(i,j)] = []
            if i - 1 >= 0 and arr[i-1][j]==".":
                graph[(i,j)].append((i-1,j))
            if j - 1 >= 0 and arr[i][j-1]==".":
                graph[(i,j)].append((i,j-1))
            if j + 1 <= m - 1 and arr[i][j+1]==".":
                graph[(i,j)].append((i,j+1))
            if i + 1 <= n - 1 and arr[i+1][j]==".":
                graph[(i,j)].append((i+1,j))
# print(graph)
def can_reach(graph, start, target):
    stack = [start]
    visited = set()
    while stack:
        current = stack.pop()
        if current == target:
            return "Yes"
        if current in visited:
            continue
        visited.add(current)
        for neighbor in graph[current]:
            if neighbor not in visited:
                stack.append(neighbor)
    return "No"
print(can_reach(graph,(0,0),(n-1,m-1)))

发表于 2025-08-28 16:08:49 回复(0)