uva 10116 的python解法

UVA 10116 题目是一个迷宫问题，可以使用深度优先搜索（DFS）来解决。下面是 Python 语言的解法：

首先定义一个 visited 数组，用于记录每个格子是否被访问过。然后从起点出发，沿着指定的方向一直走到不能走为止，直到遇到已经访问过的格子或者到达边界。如果到达边界，则输出“x step(s) to exit”，其中 x 为已经走过的步数；如果遇到已经访问过的格子，则输出“x step(s) before a loop of y step(s)” ，其中 x 为已经走过的步数，y 为环的长度。

以下是代码实现：

n, m, start = map(str, input().split())
n, m = int(n), int(m)
maze = [list(input().strip()) for _ in range(n)]
visited = [[-1] * m for _ in range(n)] # 初始值为-1
x, y = 0, int(start) - 1
steps = 0
loop_len = 0
loop_found = False

while True:
    if x < 0 or x >= n or y < 0 or y >= m:
        print(f"{steps} step(s) to exit")
        break
    if visited[x][y] != -1:
        loop_found = True
        loop_len = steps - visited[x][y]
        break

    visited[x][y] = steps
    if maze[x][y] == "N":
        x -= 1
    elif maze[x][y] == "S":
        x += 1
    elif maze[x][y] == "W":
        y -= 1
    else:
        y += 1

    steps += 1

if loop_found:
    print(f"{visited[x][y]} step(s) before a loop of {loop_len} step(s)")