23937: 逃出迷宫

http://cs101.openjudge.cn/practice/23937/

"Boom!" 小锅一觉醒来发现自己落入了一个N*N(2 <= N <= 20)的迷宫之中，为了逃出这座迷宫，小锅需要从左上角(0, 0)处的入口跑到右下角(N-1, N-1)处的出口逃出迷宫。由于小锅每一步都想缩短和出口之间的距离，所以他只会向右和向下走。假设我们知道迷宫的地图（以0代表通路，以1代表障碍），请你编写一个程序，判断小锅能否从入口跑到出口？

例如，对于下图所示的迷宫：

小锅可以如下图红线所示从迷宫左上角的入口抵达迷宫右下角的出口：

输入

第一行为一个整数N，代表迷宫的大小接下来N行为迷宫地图，迷宫地块之间以空格分隔输入保证(0, 0)和(N - 1, N - 1)处可以通过

输出

一行字符串，如果能跑到出口则输出Yes，否则输出No

样例输入

样例输出

Yes

提示

用递归解。设计函数ok(r,c)，返回True或False，表示从位置(r,c)出发能否走到终点。从(r,c）出发可以想办法往前走一步，然后看问题变成什么

题目说了只能走到0的格子，不能走到1的格子

这是模版题目，涉及到递归/dfs/回溯。一旦出现模版题目，最多是中等难度，要求必须会。

python

def dfs(mx, visited, x, y):
    # 如果到达右下角，返回True
    if x == n - 1 and y == n - 1:
        return True

    # 定义向右和向下的移动方向
    directions = [(0, 1), (1, 0)]

    for dx, dy in directions:
        nx = x + dx
        ny = y + dy
        # 检查新坐标是否在矩阵范围内，是否已经访问过，以及是否可以通过
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and mx[nx][ny] == 0:
            visited[nx][ny] = True
            if dfs(mx, visited, nx, ny):
                return True
            visited[nx][ny] = False

    return False

# 读取输入
n = int(input())
mx = [list(map(int, input().split())) for _ in range(n)]

# 初始化访问标记数组
visited = [[False] * n for _ in range(n)]

# 起始点 (0, 0) 必须是可以通过的
if mx[0][0] == 1:
    print('No')
else:
    visited[0][0] = True
    if dfs(mx, visited, 0, 0):
        print('Yes')
    else:
        print('No')

通过使用栈来模拟递归，可以避免因递归过深导致的栈溢出问题。

python

# 读取输入
n = int(input())
mx = [list(map(int, input().split())) for _ in range(n)]

# 初始化访问标记数组
visited = [[False] * n for _ in range(n)]

# 起始点 (0, 0) 必须是可以通过的
if mx[0][0] == 1:
    print('No')
else:
    # 使用栈来模拟递归
    stack = [(0, 0)]
    visited[0][0] = True

    while stack:
        x, y = stack.pop()
        
        # 如果到达右下角，返回True
        if x == n - 1 and y == n - 1:
            print('Yes')
            break

        # 定义向右和向下的移动方向
        directions = [(0, 1), (1, 0)]

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            # 检查新坐标是否在矩阵范围内，是否已经访问过，以及是否可以通过
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and mx[nx][ny] == 0:
                visited[nx][ny] = True
                stack.append((nx, ny))
    else:
        print('No')

23937: 逃出迷宫 ​

23937: 逃出迷宫