迷宫路径方案数，初学者正在写但怕弄不出来，来问问大家

Question

有一个正方形的迷宫，上面铺着正方形的瓷砖，标记为’O’的瓷砖可以在上面移动，但是标记为‘X’不可以在上面移动。一个男人从左上角移动到右下角。请写一个程序来计算他有多少种方案可以完成这个移动，要求是走过的瓷砖不能重复走，同时标记为’X’的瓷砖也不能走。

输入格式：

第一行一个整数N,表示迷宫由N*N的瓷砖铺成，N<20

接下来N行，每行N个字符，‘O’或‘X’

输出格式：

一个整数，表示移动方案数，如果大于50000则输出50000

我自己写的在VS上过了，但学习通提交超时
，然后写的深度优先搜索不对，求怎么解决呀，我已经快放弃了，能不能来个佬帮帮忙

Answer 1

该回答通过自己思路及引用到GPTᴼᴾᴱᴺᴬᴵ搜索,得到内容具体如下：
这是一个典型的搜索问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来解决。以下是一个使用DFS算法的解决方案：

n = int(input())
maze = [list(input()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

def dfs(x, y):
    if x == n-1 and y == n-1:
        return 1
    visited[x][y] = True
    res = 0
    for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:  # 向四个方向移动
        nx, ny = x+dx, y+dy
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and maze[nx][ny] == 'O':
            res += dfs(nx, ny)
    visited[x][y] = False  # 回溯
    return min(res, 50000)  # 超过50000时返回50000

print(dfs(0, 0))

首先读入迷宫和迷宫大小。然后定义一个visited数组来记录每个瓷砖是否已经走过，初始化为False。接下来定义一个dfs函数，用于搜索从当前位置出发到达终点的方案数。如果当前位置已经是终点，则返回1。否则，依次向四个方向移动，如果某个方向可以移动且未访问过且不是墙壁，则继续搜索从该位置出发到达终点的方案数。最后回溯并返回总方案数。注意，为了避免结果太大，当方案数超过50000时，返回50000。

最后调用dfs函数并输出结果即可。

---

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢